Initial commit

14 files changed, 959 insertions, 0 deletions

diff --git a/lib/knapsack_solver.rb b/lib/knapsack_solver.rb
new file mode 100644
index 0000000..9d5f19f
--- /dev/null
+++ b/lib/knapsack_solver.rb
@@ -0,0 +1,2 @@
+require 'knapsack_solver/version'
+require 'knapsack_solver/solver'
diff --git a/lib/knapsack_solver/cli.rb b/lib/knapsack_solver/cli.rb
new file mode 100644
index 0000000..716fb08
--- /dev/null
+++ b/lib/knapsack_solver/cli.rb
@@ -0,0 +1,49 @@
+require 'knapsack_solver/solver'
+require 'knapsack_solver/version'
+require 'knapsack_solver/cli_option_parser'
+require 'knapsack_solver/output_printer'
+require 'knapsack_solver/graph_printer'
+
+module KnapsackSolver
+  # This class implements a command-line interface for the 0/1 knapsack
+  # problem solver.
+  class CLI
+    # Suffix of a text file which will containg results of dataset solving
+    # (price, knapsack things presence, cpu time, wall clock time,
+    # relative_error).
+    RESULTS_FILNEMAE_SUFFIX = '.results'.freeze
+
+    # Suffix of a text file which will containg statistic data (average price,
+    # execution times, relative error)
+    STATS_FILNEMAE_SUFFIX = '.stats'.freeze
+
+    # Processes command-line arguments. If no option is given, converts arabic
+    # number to roman number and prints it to stdout.
+    #
+    # @param args [Array] the command-line arguments
+    def self.run(args)
+      options = CliOptionParser.parse(args)
+      return if options.nil?
+      datasets = args.each_with_object([]) do |file, sets|
+        sets << Dataset.parse(File.new(file))
+      end
+      s = Solver.new(options, datasets)
+      results = s.run
+      print_results(results, s.stats(results), options, args)
+    end
+
+    # Prints output of datasets solving. Results and statistics are printed to
+    # stdout or to a text files. Graphs of statistic values can be created.
+    #
+    # @param results [Hash] results of dataset solvings
+    # @param stats [Hash] statistics from the results of dataset solvings
+    # @param options [Hash] Command-line line options supplied to the CLI
+    # @param args [Array] array of the positional command-line arguments
+    def self.print_results(results, stats, options, args)
+      OutputPrinter.new(args, RESULTS_FILNEMAE_SUFFIX, results).print(options[:output_dir])
+      OutputPrinter.new(args, STATS_FILNEMAE_SUFFIX, stats).print(options[:output_dir])
+      return unless options[:graphs_dir]
+      GraphPrinter.new(args, stats, options[:graphs_dir]).print
+    end
+  end
+end
diff --git a/lib/knapsack_solver/cli_option_checker.rb b/lib/knapsack_solver/cli_option_checker.rb
new file mode 100644
index 0000000..f55dca2
--- /dev/null
+++ b/lib/knapsack_solver/cli_option_checker.rb
@@ -0,0 +1,83 @@
+require 'optparse'
+
+module KnapsackSolver
+  # This class checks command line arguments provided to the knapsack_solver
+  # binary.
+  class CliOptionChecker
+    # Checks command-line options, their arguments and positional arguments
+    # provided to the CLI.
+    #
+    # @param opts [Hash] parsed command-line options
+    # @param args [Array<String>] command-line positional arguments
+    def self.check(opts, args)
+      if !opts[:branch_and_bound] && !opts[:dynamic_programming] &&
+         !opts[:fptas] && !opts[:heuristic]
+        raise StandardError, 'At least one method of solving must be requested'
+      end
+      check_fptas_options(opts)
+      check_directories(opts)
+      check_positional_arguments(args)
+    end
+
+    # Checks command-line options and arguments used by FPTAS solving method.
+    #
+    # @param opts [Hash] parsed command-line options
+    def self.check_fptas_options(opts)
+      return if !opts[:fptas] && !opts.key?(:fptas_epsilon)
+      check_incomplete_fptas_options(opts)
+      eps = opts[:fptas_epsilon].to_f
+      return unless eps <= 0 || eps >= 1 || eps.to_s != opts[:fptas_epsilon]
+      raise StandardError,
+            'FPTAS epsilon must be number from range (0,1)'
+    end
+
+    # Checks command-line options and arguments used by FPTAS solving
+    # method. Recignizes cases when mandatory FPTAS epsilon constant is
+    # missing or when it the constant is provided and FPTAS method is not
+    # requested.
+    #
+    # @param opts [Hash] parsed command-line options
+    def self.check_incomplete_fptas_options(opts)
+      raise StandardError, 'Missing FPTAS epsilon constant' if opts[:fptas] && !opts.key?(:fptas_epsilon)
+      return unless !opts[:fptas] && opts.key?(:fptas_epsilon)
+      raise StandardError,
+            'epsilon constant must not be provided when FPTAS is not selected'
+    end
+
+    # Checks directory for result and statistic output logs, and directory for
+    # graph files.
+    #
+    # @param opts [Hash] parsed command-line options
+    def self.check_directories(opts)
+      check_output_directory(opts[:output_dir]) if opts[:output_dir]
+      check_output_directory(opts[:graphs_dir]) if opts[:graphs_dir]
+    end
+
+    # Checks if at least one dataset input file was provided and if the input
+    # files are readable.
+    #
+    # @param args [Array<String>] positional arguments provided to the CLI
+    def self.check_positional_arguments(args)
+      raise StandardError, 'Missing datset file(s)' if args.empty?
+      args.each { |f| check_input_file(f) }
+    end
+
+    # Checks if an output directory exist and is writable.
+    #
+    # @param path [Path] path to output directory
+    def self.check_output_directory(path)
+      raise StandardError, "Directory '#{path}' does not exists" unless File.exist?(path)
+      raise StandardError, "'#{path}' is not a directory" unless File.directory?(path)
+      raise StandardError, "Directory '#{path}' is not writable" unless File.writable?(path)
+    end
+
+    # Checks if an input file exist and is readable.
+    #
+    # @param path [Path] path to input regular file
+    def self.check_input_file(path)
+      raise StandardError, "File '#{path}' does not exists" unless File.exist?(path)
+      raise StandardError, "'#{path}' is not a regular file" unless File.file?(path)
+      raise StandardError, "File '#{path}' is not readable" unless File.readable?(path)
+    end
+  end
+end
diff --git a/lib/knapsack_solver/cli_option_parser.rb b/lib/knapsack_solver/cli_option_parser.rb
new file mode 100644
index 0000000..0f0720c
--- /dev/null
+++ b/lib/knapsack_solver/cli_option_parser.rb
@@ -0,0 +1,68 @@
+require 'optparse'
+require 'knapsack_solver/cli_option_checker'
+
+module KnapsackSolver
+  # This class parses command line arguments provided to the knapsack_solver
+  # binary.
+  class CliOptionParser
+    # Message that describes how to use this CLI utility.
+    USAGE_MESSAGE = 'Usage: knapsack_solver OPTIONS DATASET_FILE...'.freeze
+
+    # Parses command-line arguments and removes them from the array of
+    # arguments.
+    #
+    # @param [Array] arguments the command-line arguments.
+    # @return [Hash] hash of recognized options.
+    #
+    # rubocop:disable Metrics/AbcSize, Metric/MethodLength, Metric/BlockLength
+    def self.parse(arguments)
+      options = {}
+      parser = OptionParser.new do |opts|
+        opts.banner = USAGE_MESSAGE
+        opts.on('-b', '--branch-and-bound', 'Use branch and boung method of solving') do
+          options[:branch_and_bound] = true
+        end
+        opts.on('-d', '--dynamic-programming', 'Use dynamic programming for solving') do
+          options[:dynamic_programming] = true
+        end
+        opts.on('-f', '--fptas', 'Use FPTAS for solving') do
+          options[:fptas] = true
+        end
+        opts.on('-r', '--heuristic', 'Use brute force method of solving') do
+          options[:heuristic] = true
+        end
+        opts.on('-e', '--fptas-epsilon EPS', 'Relative error for FPTAS from range (0,1)') do |eps|
+          options[:fptas_epsilon] = eps
+        end
+        opts.on('-o', '--output DIR', 'Directory for output log files') do |dir|
+          options[:output_dir] = dir
+        end
+        opts.on('-g', '--graphs DIR', 'Directory for graphs') do |dir|
+          options[:graphs_dir] = dir
+        end
+        opts.on('-v', '--version', 'Show program version') do
+          options[:version] = true
+        end
+        opts.on_tail('-h', '--help', 'Show this help message') do
+          options[:help] = true
+        end
+      end
+      parser.parse!(arguments)
+      process_help_and_version_opts(options, arguments, parser.to_s)
+    end
+    # rubocop:enable Metrics/AbcSize, Metric/MethodLength, Metric/BlockLength
+
+    def self.process_help_and_version_opts(options, arguments, usage_msg)
+      if !options[:help] && !options[:version]
+        CliOptionChecker.check(options, arguments)
+        return options
+      end
+      if options[:help]
+        puts usage_msg
+      elsif options[:version]
+        puts "knapsack_solver #{KnapsackSolver::VERSION}"
+      end
+      nil
+    end
+  end
+end
diff --git a/lib/knapsack_solver/dataset.rb b/lib/knapsack_solver/dataset.rb
new file mode 100644
index 0000000..b38e9e5
--- /dev/null
+++ b/lib/knapsack_solver/dataset.rb
@@ -0,0 +1,44 @@
+require 'knapsack_solver/instance'
+
+module KnapsackSolver
+  # This class represents a set of 0/1 knapsack problem instances.
+  class Dataset
+    # Initializes set of 0/1 knapsack problem instances.
+    #
+    # @param id [Integer] Dataset ID number.
+    # @param instances [Array<Instance>] set of the 0/1 knapsack problem instances.
+    def initialize(id, instances)
+      @id = id
+      @instances = instances
+    end
+
+    # Parses set of a 0/1 knapsack problem instances from a character stream.
+    #
+    # @param stream [#eof?,#readline,#each_line] character stream holding the dataset.
+    # @return [Dataset] dataset instance parsed from the stream.
+    def self.parse(stream)
+      id = parse_id(stream)
+      instances = stream.each_line.with_object([]) { |l, o| o << Instance.parse(l) }
+      raise StandardError, 'dataset: missing instances' if instances.empty?
+      Dataset.new(id, instances)
+    end
+
+    # Parses ID of a 0/1 knapsack problem dataset from a character stream.
+    #
+    # @param stream [#eof?,#readline,#each_line] character stream holding the dataset.
+    # @return [Integer] dataset ID number.
+    def self.parse_id(stream)
+      raise StandardError, 'dataset: missing ID' if stream.eof?
+      s = stream.readline.split
+      raise StandardError, 'dataset: first line does not contain ID' if s.size != 1
+      begin
+        raise StandardError, 'dataset: ID is negative' if Integer(s.first) < 0
+      rescue ArgumentError
+        raise StandardError, 'dataset: ID is not an integer'
+      end
+      Integer(s.first)
+    end
+
+    attr_reader :id, :instances
+  end
+end
diff --git a/lib/knapsack_solver/graph_printer.rb b/lib/knapsack_solver/graph_printer.rb
new file mode 100644
index 0000000..318e02e
--- /dev/null
+++ b/lib/knapsack_solver/graph_printer.rb
@@ -0,0 +1,115 @@
+require 'gnuplot'
+
+module KnapsackSolver
+  # This class provides support for making graphs from statistics of datasets
+  # solving results. It uses Gnuplot and also generates a Gnuplot config file
+  # for each generated graph.
+  class GraphPrinter
+    # Initializes printer for graph data (graphs, Gnuplot config files).
+    #
+    # @param dataset_filenames [Array<String>] dataset filenames
+    # @param stats [Hash] statistics of results
+    # @param out_dir [String] statistics of results to print
+    def initialize(dataset_filenames, stats, out_dir)
+      @dataset_basenames = file_basenames(dataset_filenames)
+      @stats = stats
+      @out_dir = out_dir
+    end
+
+    # Create graphs from statistics and Gnuplot configuration files.
+    def print
+      stats_to_datasets.each do |title, ds|
+        ofn = File.join(@out_dir, title + '.png')
+        plot(title, ds, ofn)
+      end
+    end
+
+    protected
+
+    # Create graph.
+    #
+    # @param title [String] title of the graph
+    # @param data [Array<Gnuplot::DataSet>] Gnuplot datasets to plot
+    # @param filename [String] path to the output image file
+    def plot(title, data, filename)
+      Gnuplot.open do |gp|
+        Gnuplot::Plot.new(gp, &plot_config(title, 'dataset', 'y', data, filename))
+      end
+      File.open(File.join(File.dirname(filename), File.basename(filename, '.png') + '.gnuplot'), 'w') do |gp|
+        Gnuplot::Plot.new(gp, &plot_config(title, 'dataset', 'y', data, filename))
+      end
+    end
+
+    # Creates Gnuplot datasets from statistics.
+    #
+    # @return [Array<Gnuplot::DataSet>] Gnuplot datasets created from the statistics.
+    def stats_to_datasets
+      graphs = @stats.values.first.values.first.first.keys
+      x_data = @stats.keys
+      datasets(graphs, x_data)
+    end
+
+    # Creates Gnuplot datasets from statistics.
+    #
+    # @param graphs [Array] array of graph titles
+    # @param x_data [Array] array of X axis values
+    def datasets(graphs, x_data)
+      graphs.each_with_object({}) do |g, gnuplot_datasets|
+        @stats.each_value do |s|
+          gnuplot_datasets[g.to_s] = s.each_key.with_object([]) do |method, o|
+            o << plot_dataset(method.to_s, x_data, @stats.map { |_, v| v[method].first[g] })
+          end
+        end
+      end
+    end
+
+    # Create dataset from provided title, X axis data and Y axis data.
+    #
+    # @param title [String] Gnuplot dataset title
+    # @param x_data [Array] Array of X values
+    # @param y_data [Array] Array of Y values
+    # @return [Gnuplot::DataSet] Gnuplot dataset.
+    def plot_dataset(title, x_data, y_data)
+      Gnuplot::DataSet.new([x_data, y_data]) { |ds| ds.title = escape_gnuplot_special_chars(title) }
+    end
+
+    # Creates Gnuplot plot configuration (configuration text lines).
+    #
+    # @param title [String] graph title
+    # @param xlabel [String] label of X axis
+    # @param ylabel [String] label of Y axis
+    # @param plot_datasets [Array<Gnuplot::DataSet>] Gnuplot datasets for plotting
+    # @param out_file [String] output file
+    # @return [lambda] Lambda for setting plot configuration.
+    def plot_config(title, xlabel, ylabel, plot_datasets, out_file)
+      lambda do |plot|
+        plot.term('png')
+        plot.output(out_file)
+        plot.title("'#{escape_gnuplot_special_chars(title)}'")
+        plot.ylabel("'#{escape_gnuplot_special_chars(ylabel)}'")
+        plot.xlabel("'#{escape_gnuplot_special_chars(xlabel)}'")
+        plot.key('outside')
+        plot.data = plot_datasets
+      end
+    end
+
+    # Escapes Gnuplot special characters.
+    #
+    # @param str [String] a string
+    # @return [Strnig] the string with Gnuplot special chars escaped
+    def escape_gnuplot_special_chars(str)
+      # underscore means subscript in Gnuplot
+      str.gsub('_', '\_')
+    end
+
+    # Gets basenames of supplied file paths.
+    #
+    # @param paths [Array<String>] path to files
+    # @return [Array<String>] basenames of the paths
+    def file_basenames(paths)
+      paths.each_with_object([]) do |path, basenames|
+        basenames << File.basename(path, File.extname(path))
+      end
+    end
+  end
+end
diff --git a/lib/knapsack_solver/instance.rb b/lib/knapsack_solver/instance.rb
new file mode 100644
index 0000000..1fe3ecc
--- /dev/null
+++ b/lib/knapsack_solver/instance.rb
@@ -0,0 +1,48 @@
+module KnapsackSolver
+  # This class represents an instance of a 0/1 knapsack problem.
+  class Instance
+    # Initializes instance of a 0/1 knapsack problem.
+    #
+    # @param capacity [Integer] weight capacity of the knapsack
+    # @param things [Array<Thing>] things which can be put into the knapsack
+    def initialize(capacity, things)
+      @weight_capacity = capacity
+      @things = things
+    end
+
+    # Creates new instance of a 0/1 knapsack problem.
+    #
+    # @param line [String] line that describes an instance of a 0/1 knapsack problem
+    # @return [Instance] instance of the 0/1 knapsack problem
+    def self.parse(line)
+      thing = Struct.new(:price, :weight, :index)
+      # Rozdelit riadok na slova a previest na cisla
+      items = split_line(line)
+      # Inicializacia premennych
+      things = items.drop(1).each_slice(2).with_index.each_with_object([]) do |(s, i), o|
+        o << thing.new(s[0], s[1], i)
+      end
+      Instance.new(items[0], things)
+    end
+
+    # Splits line that describes an instance of a 0/1 knapsack problem to
+    # individual numbers.
+    #
+    # @param line [String] line that describes an instance of a 0/1 knapsack problem
+    # @return [Array<Integer>] integer numbers from the line
+    def self.split_line(line)
+      items = line.split.map! do |i|
+        n = Integer(i)
+        raise StandardError, 'dataset: instance desctiption contains negative number' if n < 0
+        n
+      end
+      raise StandardError, 'dataset: missing knapsack capacity' if items.empty?
+      raise StandardError, 'dataset: missing pairs (price, weight)' if items.size.even?
+      items
+    rescue ArgumentError
+      raise StandardError, 'dataset: instance desctiption does not contain only integers'
+    end
+
+    attr_reader :weight_capacity, :things
+  end
+end
diff --git a/lib/knapsack_solver/output_printer.rb b/lib/knapsack_solver/output_printer.rb
new file mode 100644
index 0000000..8ed857a
--- /dev/null
+++ b/lib/knapsack_solver/output_printer.rb
@@ -0,0 +1,97 @@
+module KnapsackSolver
+  # This class provides support for printing results and statistics of a
+  # dataset solving either to stdout or to a text file.
+  class OutputPrinter
+    # Initializes printer for output log (results, statistics).
+    #
+    # @param dataset_filenames [Array<String>] dataset filenames
+    # @param suffix [String] suffix of the created files
+    # @param results [Hash] results of solving or statistics to print
+    def initialize(dataset_filenames, suffix, results)
+      @dataset_basenames = file_basenames(dataset_filenames)
+      @suffix = suffix
+      @results = results
+    end
+
+    # Prints results or statistics to stdout or to files in output directory.
+    #
+    # @param out_dir [String] path to output directory
+    def print(out_dir = nil)
+      @results.each_value.with_index do |results, index|
+        results.each do |method, res|
+          print_solving_method_results(method, res, out_dir, @dataset_basenames[index])
+        end
+      end
+    end
+
+    protected
+
+    # Prints results of solving or statistics.
+    #
+    # @param method [Symbol] symbol for solving method
+    # @param res [Hash] results of the solving method
+    # @param out_dir [String] path to output directory
+    # @param basename [String] basename of dataset input file corresponding to the results
+    def print_solving_method_results(method, res, out_dir, basename)
+      of = output_filename(out_dir, basename, method.to_s)
+      os = output_stream(out_dir, of)
+      print_header(os, of, res)
+      res.each do |r|
+        os.puts r.values.each_with_object([]) { |v, a| a << v.to_s }.join(' ')
+      end
+      os.puts if out_dir.nil?
+    end
+
+    # Opens output file and turns on synchronized writes (this is neede for
+    # testing with Rspec).
+    #
+    # @param fname [String] path to the output file
+    # @return [#puts] output stream
+    def open_output_file(fname)
+      f = File.new(fname, 'w')
+      f.sync = true
+      f
+    end
+
+    # Sets output stream to stdout or to a file if path to it was provided.
+    #
+    # @param out_dir [String] directory for output files
+    # @param out_file [String] output file
+    def output_stream(out_dir, out_file)
+      return $stdout if out_dir.nil?
+      open_output_file(out_file)
+    end
+
+    # Prints header of output log file.
+    #
+    # @param out_stream [#puts] stream to which output will be printed
+    # @param out_file [String] name of output file
+    # @param results [Hash] results of solving or statistics
+    def print_header(out_stream, out_file, results)
+      out_stream.puts "# #{out_file}"
+      out_stream.puts "# #{results.first.keys.join('    ')}"
+    end
+
+    # Gets basenames of supplied file paths.
+    #
+    # @param paths [Array<String>] path to files
+    # @return [Array<String>] basenames of the paths
+    def file_basenames(paths)
+      paths.each_with_object([]) do |path, basenames|
+        basenames << File.basename(path, File.extname(path))
+      end
+    end
+
+    # Construct filename for output log.
+    #
+    # @param output_dir [String] output directory
+    # @param basename [String] basename of the output file
+    # @param solving_method [String] name of solving method
+    # @return [String] filename for output log
+    def output_filename(output_dir, basename, solving_method)
+      filename = basename + '_' + solving_method + @suffix
+      return filename if output_dir.nil?
+      File.join(output_dir, filename)
+    end
+  end
+end
diff --git a/lib/knapsack_solver/solver.rb b/lib/knapsack_solver/solver.rb
new file mode 100644
index 0000000..c392d69
--- /dev/null
+++ b/lib/knapsack_solver/solver.rb
@@ -0,0 +1,118 @@
+require 'benchmark'
+
+require 'knapsack_solver/dataset'
+require 'knapsack_solver/solving_methods/heuristic_price_weight'
+require 'knapsack_solver/solving_methods/branch_and_bound'
+require 'knapsack_solver/solving_methods/dynamic_programming'
+require 'knapsack_solver/solving_methods/fptas'
+
+module KnapsackSolver
+  # This class solves datasets of 0/1 knapsack problem instances using a
+  # requested solving methods. It measures execution time of a solving and
+  # computes relative error if some exact solving method is requested.
+  class Solver
+    # Initializes solver for use of user selected solving methods.
+    #
+    # @param opts [Hash] parser command-line options
+    # @param datasets [Hash] parsed sets of 0/1 knapsack problem instances
+    def initialize(opts, datasets)
+      @opts = opts
+      @datasets = datasets
+      @solver_objects = {}
+      { branch_and_bound: 'KnapsackSolver::BranchAndBound',
+        dynamic_programming: 'KnapsackSolver::DynamicProgramming',
+        heuristic: 'KnapsackSolver::HeuristicPriceToWeight',
+        fptas: 'KnapsackSolver::Fptas' }.each do |symbol, class_name|
+        @solver_objects[symbol] = Object.const_get(class_name) if opts[symbol]
+      end
+    end
+
+    # Solve datasets using all selected method of solving, measure their
+    # execution time and compute relative errors if some exact method was
+    # requested.
+    #
+    # @return [Hash] results of dataset solving
+    def run
+      results = @datasets.each_with_object({}) do |dataset, res|
+        res[dataset.id] = @solver_objects.each_with_object({}) do |(solver, object), r|
+          r[solver] = dataset.instances.each_with_object([]) do |inst, a|
+            o = object.new(inst) unless solver == :fptas
+            o = object.new(inst, @opts[:fptas_epsilon]) if solver == :fptas
+            a << execution_time { o.run }
+          end
+        end
+      end
+      add_relative_error(results)
+    end
+
+    # Creates statistics (average price, execution times, relative error) from
+    # results of solving.
+    #
+    # @param results [Hash] solving results of datasets and solving methods
+    # @return [Hash] statistics for datasets and solving methods
+    def stats(results)
+      results.each_with_object({}) do |(dataset_id, method_results), q|
+        q[dataset_id] = method_results.each_with_object({}) do |(met, res), p|
+          p[met] = averages(res)
+        end
+      end
+    end
+
+    protected
+
+    # Computes average values from the results.
+    #
+    # @param res [Hash] results for one dataset and one method
+    # @return [Array<Hash>] array of computed average values
+    def averages(res)
+      [res.first.keys.reject { |k| k == :config }.each_with_object({}) do |v, o|
+         values = res.map { |i| i[v] }
+         o[('avg_' + v.to_s).to_sym] = values.reduce(:+).to_f / values.size
+       end]
+    end
+
+    # Adds relative error to results of solving if some exact method of
+    # solving was requested.
+    #
+    # @param results [Hash] results of solving using requested methods
+    # @return [Hash] the results with relative error added
+    def add_relative_error(results)
+      return results unless @opts[:branch_and_bound] || @opts[:dynamic_programming]
+      exact_method = @opts[:branch_and_bound] ? :branch_and_bound : :dynamic_programming
+      results.each_value do |method_results|
+        method_results.each_value do |res|
+          res.each_with_index do |r, i|
+            r[:relative_error] = relative_error(method_results[exact_method][i][:price], r[:price])
+          end
+        end
+      end
+      results
+    end
+
+    # Measure execution time of provided block so that measured time is non-zero.
+    #
+    # @yieldparam block for which execution time will be measured
+    # @return [Hash] solving results with cpu time and wall clock time of execution
+    def execution_time
+      exec_count = 1
+      result = nil
+      cpu_time = wall_clock_time = 0.0
+      while cpu_time.zero? || wall_clock_time.zero?
+        b = Benchmark.measure { exec_count.times { result = yield } }
+        cpu_time += b.total
+        wall_clock_time += b.real
+        exec_count *= 2
+      end
+      result.merge(cpu_time: cpu_time, wall_clock_time: wall_clock_time)
+    end
+
+    # Computes relative error of approximate solution.
+    #
+    # @param opt [Numeric] Optimal price.
+    # @param apx [Numeric] Approximate price.
+    # @return [Float] Relative error.
+    def relative_error(opt, apx)
+      (opt.to_f - apx.to_f) / opt.to_f
+    end
+  end
+end
diff --git a/lib/knapsack_solver/solving_methods/branch_and_bound.rb b/lib/knapsack_solver/solving_methods/branch_and_bound.rb
new file mode 100644
index 0000000..64d7092
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/branch_and_bound.rb
@@ -0,0 +1,111 @@
+module KnapsackSolver
+  # This class implements methods for solving 0/1 knapsack problem using
+  # Branch and Bound method.
+  class BranchAndBound
+    # Initializes instance of Brand and Bound 0/1 knapsack problem solver.
+    #
+    # @param instance [Instance] 0/1 knapsack problem instance
+    def initialize(instance)
+      @instance = instance
+      @config = Array.new(instance.things.size)
+    end
+
+    # Solve the instance of 0/1 knapsack problem.
+    #
+    # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)
+    def run
+      solve(0)
+      { price: @best_price, config: @best_config }
+    end
+
+    protected
+
+    # Solve the problem starting at specified thing.
+    #
+    # @param index [Integer] index of thing which will be decided (put in or out from the knapsack) the next
+    def solve(index)
+      @config[index] = 0
+      solve(index + 1) unless stop(index)
+      @config[index] = 1
+      solve(index + 1) unless stop(index)
+    end
+
+    # Determine if solving of current branch should continue.
+    #
+    # @param index [Integer] index of the last decided thing so far
+    # @return [true, false] weather to continue with solving current branch.
+    def stop(index)
+      # Update of the best price so far
+      weight = config_weight(0, index)
+      price = config_price(0, index)
+      update_best_price(price, weight, index)
+      # No more things to put into the knapsack
+      return true if index >= (@instance.things.size - 1)
+      # The knapsack is overloaded, do not continue this branch
+      return true if weight > @instance.weight_capacity
+      if instance_variable_defined?('@best_price') &&
+         ((price + get_price_of_remaining_things(index + 1)) <= @best_price)
+        # Adding all the ramining things does not produce better price
+        return true
+      end
+      false
+    end
+
+    # Update the best price achieved so far.
+    #
+    # @param price [Integer] price of the current configuration
+    # @param weight [Integer] weight of the current configuration
+    # @param index [Integer] index of the next thing presence of which will be decided
+    def update_best_price(price, weight, index)
+      if !instance_variable_defined?('@best_price') ||
+         ((weight <= @instance.weight_capacity) && (price > @best_price))
+        @best_price = price
+        valid_len = index + 1
+        remaining = @config.size - index - 1
+        # All undecided things will not be put into the knapsack
+        @best_config = @config.slice(0, valid_len).fill(0, valid_len, remaining)
+        @best_config_index = index
+      end
+    end
+
+    # Gets weight of set of things. The set is subset of the things ordered by
+    # their index.
+    #
+    # @param start_index [Integer] index of the first thing included in the set
+    # @param end_index [Integer] index of the last thing included in the set
+    # @return [Integer] weight of the things
+    def config_weight(start_index, end_index)
+      weight = 0
+      @config[start_index..end_index].each_with_index do |presence, index|
+        weight += presence * @instance.things[index].weight
+      end
+      weight
+    end
+
+    # Gets price of set of things. The set is subset of the things ordered by
+    # their index.
+    #
+    # @param start_index [Integer] index of the first thing included in the set
+    # @param end_index [Integer] index of the last thing included in the set
+    # @return [Integer] price of the things
+    def config_price(start_index, end_index)
+      price = 0
+      @config[start_index..end_index].each_with_index do |presence, index|
+        price += presence * @instance.things[index].price
+      end
+      price
+    end
+
+    # Gets sum of prices of things for which their presence in the knapsack
+    # was not decided yet.
+    #
+    # @param from_index [Integer] index of the first undecided thing
+    # @return [Integer] price of the remaining things
+    def get_price_of_remaining_things(from_index)
+      price = 0
+      to_index = @instance.things.size - 1
+      @instance.things[from_index..to_index].each { |t| price += t.price }
+      price
+    end
+  end
+end
diff --git a/lib/knapsack_solver/solving_methods/dynamic_programming.rb b/lib/knapsack_solver/solving_methods/dynamic_programming.rb
new file mode 100644
index 0000000..756a9a6
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/dynamic_programming.rb
@@ -0,0 +1,116 @@
+module KnapsackSolver
+  # This class implements methods for solving 0/1 knapsack problem using
+  # dynamic programming with decomposition by price.
+  class DynamicProgramming
+    # Initializes instance of 0/1 knapsack problem solver based on dynamic
+    # programming with decomposition by price.
+    #
+    # @param instance [Instance] 0/1 knapsack problem instance
+    def initialize(instance)
+      @instance = instance
+      @config = Array.new(instance.things.size)
+    end
+
+    # Solve the instance of 0/1 knapsack problem.
+    #
+    # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)
+    def run
+      solve
+      { price: @best_price, config: @best_config }
+    end
+
+    protected
+
+    # Solve the instance of 0/1 knapsack problem using dynamic programming.
+    def solve
+      # Dynamic programming table
+      c = all_things_price + 1 # height of array from 0 to max. price
+      n = @instance.things.size + 1 # width of array, from 0th thing to Nth
+      # Value used as infinity in the dynamic programming table
+      @infinity = (all_things_weight + 1).freeze
+      @weight_array = Array.new(n) { Array.new(c, @infinity) }
+      @weight_array[0][0] = 0
+      fill_table
+      find_best_price
+      configuration_vector
+    end
+
+    # Fill the dynamic programming table.
+    def fill_table
+      (1..@instance.things.size).each do |ni|
+        (0..all_things_price).each do |ci|
+          @weight_array[ni][ci] = minimum_weight(ni, ci)
+        end
+      end
+    end
+
+    # Find the value of cell in dynamic programming table.
+    #
+    # @param ni [Integer] X axis coordinate
+    # @param ci [Integer] Y axis coordinate
+    # @return [Integer]
+    def minimum_weight(ni, ci)
+      b = weight_of(ni - 1, ci - @instance.things[ni - 1].price)
+      b += @instance.things[ni - 1].weight
+      [weight_of(ni - 1, ci), b].min
+    end
+
+    # Find the best price from the filled dynamic programming table.
+    def find_best_price
+      @best_price = @weight_array.last[0]
+      (1..all_things_price).each do |i|
+        @best_price = i if @weight_array.last[i] <= @instance.weight_capacity
+      end
+    end
+
+    # Reconstructs configuration vector from dynamic programming table.
+    def configuration_vector
+      @best_config = []
+      ci = @best_price
+      @instance.things.size.downto(1) do |i|
+        ci = determine_config_variable(i, ci)
+      end
+    end
+
+    # Determine value of one scalar for the configuration vector.
+    #
+    # return [Integer] next Y index to the dynamic programming table
+    def determine_config_variable(i, ci)
+      if @weight_array[i][ci] == @weight_array[i - 1][ci]
+        @best_config[i - 1] = 0
+      else
+        @best_config[i - 1] = 1
+        ci -= @instance.things[i - 1].price
+      end
+      ci
+    end
+
+    # Gets weight from dynamic programming table.
+    #
+    # @param i [Integer] Y index of dynamic programming table
+    # @param c [Integer] X index of dynamic programming table
+    # @return [Integer] the value from the array
+    def weight_of(i, c)
+      return @infinity if (i < 0) || (c < 0)
+      @weight_array[i][c]
+    end
+
+    # Computes total price of all things of the instance.
+    #
+    # @return [Integer] total price
+    def all_things_price
+      price = 0
+      @instance.things.each { |t| price += t.price }
+      price
+    end
+
+    # Computes total weight of all things of the instance.
+    #
+    # @return [Integer] total weight
+    def all_things_weight
+      weight = 0
+      @instance.things.each { |t| weight += t.weight }
+      weight
+    end
+  end
+end
diff --git a/lib/knapsack_solver/solving_methods/fptas.rb b/lib/knapsack_solver/solving_methods/fptas.rb
new file mode 100644
index 0000000..55ee52f
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/fptas.rb
@@ -0,0 +1,47 @@
+require 'knapsack_solver/solving_methods/dynamic_programming'
+
+module KnapsackSolver
+  # This class implements methods for solving 0/1 knapsack problem using Fully
+  # Polynomial Time Approximation Scheme.
+  class Fptas
+    # Initializes 0/1 knapsack FPTAS solver.
+    #
+    # @param instance [Instance] Instance of a 0/1 knapsack problem.
+    # @param epsilon [Instances] Maximum allowed relative error of the resulting price.
+    def initialize(instance, epsilon)
+      @instance = instance
+      @epsilon = epsilon.to_f
+      @orig_prices = @instance.things.map(&:price)
+    end
+
+    # Solve the instance of 0/1 knapsack problem using FPTAS.
+    #
+    # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)
+    def run
+      modify_prices_for_epsilon!
+      r = DynamicProgramming.new(@instance).run
+      p = get_normal_price_from_fptas(r[:config])
+      { price: p, config: r[:config] }
+    end
+
+    protected
+
+    # Modifies prices of the things according to the supplied epsilon constant
+    # to achieve max. allowed relative error.
+    def modify_prices_for_epsilon!
+      m = @instance.things.max_by(&:price).price
+      k = (@epsilon * m) / @instance.things.size
+      @instance.things.each { |t| t.price = (t.price.to_f / k).floor }
+    end
+
+    # Computes resulting price using original unmodified prices of things.
+    #
+    # @param presenve [Array] configuration variables vector
+    # @return [Integer] total price of things in the knapsack
+    def get_normal_price_from_fptas(presence)
+      @instance.things.reduce(0) do |price, t|
+        price + ((presence[t.index] != 0 ? @orig_prices[t.index] : 0))
+      end
+    end
+  end
+end
diff --git a/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb b/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb
new file mode 100644
index 0000000..8f694fc
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb
@@ -0,0 +1,56 @@
+module KnapsackSolver
+  # This class implements methods for solving 0/1 knapsack problem using
+  # simple heuristic by price to weight ratio. Things with the best price to
+  # weight ratio are selected first.
+  class HeuristicPriceToWeight
+    # Initializes instance of 0/1 knapsack problem solver using simple
+    # heuristic by price to weight ratio.
+    #
+    # @param instance [Instance] 0/1 knapsack problem instance
+    def initialize(instance)
+      @instance = instance
+      @config = Array.new(instance.things.size) { 0 }
+      @sorted_things = instance.things.sort do |a, b|
+        (b.price.to_f / b.weight) <=> (a.price.to_f / a.weight)
+      end
+    end
+
+    # Solve the instance of 0/1 knapsack problem.
+    #
+    # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)
+    def run
+      solve
+      { price: @best_price, config: @best_config }
+    end
+
+    protected
+
+    # Solve the instance of 0/1 knapsack problem.
+    def solve
+      @sorted_things.each do |thing|
+        break if (config_weight + thing.weight) > @instance.weight_capacity
+        @config[thing.index] = 1
+      end
+      @best_price = config_price
+      @best_config = @config.dup
+    end
+
+    # Gets total weight of things present in the knapsack.
+    #
+    # @return [Integer] total weight
+    def config_weight
+      @config.each_with_index.reduce(0) do |weight, (presence, index)|
+        weight + presence * @instance.things[index].weight
+      end
+    end
+
+    # Gets total price of things present in the knapsack.
+    #
+    # @return [Integer] total price
+    def config_price
+      @config.each_with_index.reduce(0) do |price, (presence, index)|
+        price + presence * @instance.things[index].price
+      end
+    end
+  end
+end
diff --git a/lib/knapsack_solver/version.rb b/lib/knapsack_solver/version.rb
new file mode 100644
index 0000000..3b87713
--- /dev/null
+++ b/lib/knapsack_solver/version.rb
@@ -0,0 +1,5 @@
+# Namespace for classes and modules for 0/1 knapsack problem utility.
+module KnapsackSolver
+  # Version of this comman-line utility for solving 0/1 knapsack problem.
+  VERSION = '0.1.0'.freeze
+end