Initial commit

45 files changed, 1490 insertions, 0 deletions

diff --git a/.rubocop.yml b/.rubocop.yml
new file mode 100644
index 0000000..bf31b8e
--- /dev/null
+++ b/.rubocop.yml
@@ -0,0 +1,2 @@
+Metrics/LineLength:
+   Max: 120
diff --git a/Gemfile b/Gemfile
new file mode 100644
index 0000000..4c5c0c9
--- /dev/null
+++ b/Gemfile
@@ -0,0 +1,4 @@
+source 'https://rubygems.org'
+
+# Dependencies of this gem are in .gemspec.
+gemspec
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..4af7772
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,19 @@
+Copyright (c) 2018, Ján Sučan
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/Rakefile b/Rakefile
new file mode 100644
index 0000000..9a5f79e
--- /dev/null
+++ b/Rakefile
@@ -0,0 +1,13 @@
+require 'rake'
+require 'rspec/core/rake_task'
+require 'rubocop/rake_task'
+
+RSpec::Core::RakeTask.new(:spec) do |t|
+    t.pattern = Dir.glob('test/**/*_spec.rb')
+end
+
+RuboCop::RakeTask.new(:rubocop) do |t|
+    t.patterns = Dir.glob('lib/**/*.rb')
+end
+
+task default: :spec
diff --git a/bin/knapsack_solver b/bin/knapsack_solver
new file mode 100644
index 0000000..2e2de9d
--- /dev/null
+++ b/bin/knapsack_solver
@@ -0,0 +1,12 @@
+#!/usr/bin/env ruby
+
+require 'knapsack_solver/cli'
+
+begin
+  KnapsackSolver::CLI.run(ARGV)
+  exit 0
+rescue StandardError => e
+  STDERR.puts "ERROR: #{e.message}"
+  STDERR.puts "Try 'knapsack_solver --help' for more information."
+  exit 1
+end
diff --git a/knapsack_solver.gemspec b/knapsack_solver.gemspec
new file mode 100644
index 0000000..8a3bf4d
--- /dev/null
+++ b/knapsack_solver.gemspec
@@ -0,0 +1,33 @@
+require File.expand_path('lib/knapsack_solver/version', __dir__)
+
+Gem::Specification.new do |s|
+  s.name        = 'knapsack_solver'
+  s.version     = KnapsackSolver::VERSION
+  s.homepage    = 'https://github.com/sucanjan/knapsack-solver'
+  s.license     = 'MIT'
+  s.author      = 'Jan Sucan'
+  s.email       = 'sucanjan@fit.cvut.cz'
+
+  s.summary     = '0/1 knapsack problem solver.'
+  s.description = <<-EOF
+This gem contains command-line utility for solving 0/1 knapsack problem using
+branch-and-bound method, dynamic programming, simple heuristic (weight/price)
+and fully polynomial time approximation scheme.
+
+It can measure CPU and wall-clock time spent by solving a problem, compute
+relative error of the result and generate graphs from those values.
+EOF
+
+  s.files       = Dir['bin/*', 'lib/**/*', '*.gemspec', 'LICENSE*', 'README*', 'test/*']
+  s.executables = Dir['bin/*'].map { |f| File.basename(f) }
+  s.has_rdoc    = 'yard'
+
+  s.required_ruby_version = '>= 2.2'
+  
+  s.add_runtime_dependency 'gnuplot', '~> 2.6'
+
+  s.add_development_dependency 'rake', '~> 12.0'
+  s.add_development_dependency 'rspec', '~> 3.6'
+  s.add_development_dependency 'rubocop', '~> 0.50.0'
+  s.add_development_dependency 'yard', '~> 0.9'
+end
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
diff --git a/test/datasets/size_10.dataset b/test/datasets/size_10.dataset
new file mode 100644
index 0000000..bcf3857
--- /dev/null
+++ b/test/datasets/size_10.dataset
@@ -0,0 +1,4 @@
+10
+100 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 100 99
+100 5 225 2 248 8 189 7 221 68 228 6 31 1 91 12 140 21 112 22 118
+100 2 125 1 239 35 223 4 145 7 249 19 78 12 174 3 125 34 221 11 93
diff --git a/test/datasets/size_4.dataset b/test/datasets/size_4.dataset
new file mode 100644
index 0000000..0ae0363
--- /dev/null
+++ b/test/datasets/size_4.dataset
@@ -0,0 +1,4 @@
+4
+100 65 38 20 243 13 107 39 122
+100 21 29 17 190 86 88 52 95
+100 64 155 20 62 52 56 2 170
diff --git a/test/invalid_datasets/invalid_1.dataset b/test/invalid_datasets/invalid_1.dataset
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/invalid_datasets/invalid_1.dataset
diff --git a/test/invalid_datasets/invalid_2.dataset b/test/invalid_datasets/invalid_2.dataset
new file mode 100644
index 0000000..7b6743e
--- /dev/null
+++ b/test/invalid_datasets/invalid_2.dataset
@@ -0,0 +1,3 @@
+100 65 38 20 243 13 107 39 122
+100 21 29 17 190 86 88 52 95
+100 64 155 20 62 52 56 2 170
diff --git a/test/invalid_datasets/invalid_3.dataset b/test/invalid_datasets/invalid_3.dataset
new file mode 100644
index 0000000..f56eb9a
--- /dev/null
+++ b/test/invalid_datasets/invalid_3.dataset
@@ -0,0 +1,4 @@
+-4
+100 65 38 20 243 13 107 39 122
+100 21 29 17 190 86 88 52 95
+100 64 155 20 62 52 56 2 170
diff --git a/test/invalid_datasets/invalid_4.dataset b/test/invalid_datasets/invalid_4.dataset
new file mode 100644
index 0000000..f976d55
--- /dev/null
+++ b/test/invalid_datasets/invalid_4.dataset
@@ -0,0 +1,4 @@
+4.2
+100 65 38 20 243 13 107 39 122
+100 21 29 17 190 86 88 52 95
+100 64 155 20 62 52 56 2 170
diff --git a/test/invalid_datasets/invalid_5.dataset b/test/invalid_datasets/invalid_5.dataset
new file mode 100644
index 0000000..733787e
--- /dev/null
+++ b/test/invalid_datasets/invalid_5.dataset
@@ -0,0 +1,2 @@
+4
+
diff --git a/test/invalid_datasets/invalid_6.dataset b/test/invalid_datasets/invalid_6.dataset
new file mode 100644
index 0000000..3d81f69
--- /dev/null
+++ b/test/invalid_datasets/invalid_6.dataset
@@ -0,0 +1,2 @@
+4
+100 65 38 20 243 13 107 39
diff --git a/test/invalid_datasets/invalid_7.dataset b/test/invalid_datasets/invalid_7.dataset
new file mode 100644
index 0000000..19bc569
--- /dev/null
+++ b/test/invalid_datasets/invalid_7.dataset
@@ -0,0 +1,4 @@
+4
+100 65 38 20 243 13 107 39 122
+100 21 29 17 190 86 88 52 95
+100 -64 155 20 62 52 56 2 170
diff --git a/test/invalid_datasets/invalid_8.dataset b/test/invalid_datasets/invalid_8.dataset
new file mode 100644
index 0000000..3a94b69
--- /dev/null
+++ b/test/invalid_datasets/invalid_8.dataset
@@ -0,0 +1,4 @@
+4
+100 65 38 20 243 13 107 39 122
+100 21 29 17 190 86 88.888 52 95
+100 64 155 20 62 52 56 2 170
diff --git a/test/knapsack_solver_matchers.rb b/test/knapsack_solver_matchers.rb
new file mode 100644
index 0000000..754fb20
--- /dev/null
+++ b/test/knapsack_solver_matchers.rb
@@ -0,0 +1,103 @@
+require 'rspec/expectations'
+
+def comment_lines(file_path)
+  File.open(file_path, 'r').each_line.select { |l| l.chars.first == '#' }
+end
+
+def data_lines(file_path)
+  File.open(file_path, 'r').each_line.select { |l| l.chars.first != '#' }
+end
+
+
+RSpec::Matchers.define :be_a_regular_file do
+  match do |actual|
+    File.file?(actual)
+  end
+end
+
+RSpec::Matchers.define :be_an_empty_directory do
+  match do |actual|
+    Dir.empty?(actual)
+  end
+end
+
+RSpec::Matchers.define :be_a_valid_results_file do
+  match do |actual|
+    begin
+      comment_lines = comment_lines(actual)
+      data_lines = data_lines(actual)
+      # It must have 3 lines: 2 comments and >= 1 data line
+      return false if comment_lines.size != 2 || data_lines.size < 1
+      # Data line must consist of non-negative numbers and array 1 and 0
+      data_lines.each do |l|
+        l.scan(/\[[^\]]*\]/).first.tr('[]', '').split(',').map { |n| n.to_i }.each do |i|
+          return false if i != 0 && i != 1
+        end
+        l.scan(/[0-9\.]+/).map { |n| n.to_f }.each do |i|
+          return false if i < 0
+        end
+      end
+      true
+    rescue
+      false
+    end
+  end
+end  
+
+RSpec::Matchers.define :be_a_equal_to_results_file do |good|
+  match do |actual|
+    begin
+      lines = data_lines(actual)
+      good_lines = data_lines(good)
+      return false if lines.size != good_lines.size
+      lines.each_with_index do |l, i|
+        # Check price and configuration
+        return false if l.split(']').first != good_lines[i].split(']').first
+        # Check relative error
+        return false if l.split().last != good_lines[i].split().last
+        return false if l.split().size != good_lines[i].split().size
+      end
+      true
+    rescue
+      false
+    end
+  end
+end
+
+RSpec::Matchers.define :be_a_equal_to_stats_file do |good|
+  match do |actual|
+    begin
+      lines = data_lines(actual)
+      good_lines = data_lines(good)
+      return false if lines.size != good_lines.size
+      lines.each_with_index do |l, i|
+        # Check average price
+        return false if l.split().first != good_lines[i].split().first
+        # Check average relative error
+        return false if l.split().last != good_lines[i].split().last
+        return false if l.split().size != good_lines[i].split().size
+      end
+      true
+    rescue
+      false
+    end
+  end
+end
+
+RSpec::Matchers.define :be_a_valid_stats_file do
+  match do |actual|
+    begin
+      comment_lines = comment_lines(actual)
+      data_lines = data_lines(actual)
+      # It must have 3 lines: 2 comments and 1 data line
+      return false if comment_lines.size != 2 || data_lines.size != 1
+      # Data line must consist of non-negative numbers
+      data_lines.first.split.map { |i| i.to_f }.each do |n|
+        return false if n < 0
+      end
+      true
+    rescue
+      false
+    end
+  end
+end
diff --git a/test/knapsack_solver_spec.rb b/test/knapsack_solver_spec.rb
new file mode 100644
index 0000000..9b825a6
--- /dev/null
+++ b/test/knapsack_solver_spec.rb
@@ -0,0 +1,261 @@
+require 'rspec'
+require 'tmpdir'
+require_relative 'spec_helper'
+require_relative 'knapsack_solver_matchers'
+require_relative '../lib/knapsack_solver/cli.rb'
+require_relative '../lib/knapsack_solver/version.rb'
+
+module FileHelper
+  def file_list(directory, files)
+    files.map { |f| File.join(directory, f) }
+  end
+end
+
+module ArgumentHelper
+  def args(args_string = nil)
+    return [] if args_string.nil?
+    args_string.split
+  end
+
+  def args_in_dataset_out_file(args_string, tmpdir)
+    args(args_string) + ['-o', tmpdir, 'test/datasets/size_4.dataset', 'test/datasets/size_10.dataset']
+  end
+end
+
+describe KnapsackSolver::CLI do
+  include FileHelper
+  include ArgumentHelper
+
+  subject(:cli) { KnapsackSolver::CLI }
+
+  context 'options' do
+    it 'recognizes invalid options' do
+      expect { cli.run(args('-a')) }.to raise_error(OptionParser::InvalidOption)
+      expect { cli.run(args('-k -h')) }.to raise_error(OptionParser::InvalidOption)
+      expect { cli.run(args('-x -b')) }.to raise_error(OptionParser::InvalidOption)
+    end
+
+    it 'detects missing arguments' do
+      expect { cli.run(args('-o')) }.to raise_error(OptionParser::MissingArgument)
+      expect { cli.run(args('-g')) }.to raise_error(OptionParser::MissingArgument)
+    end
+    
+    it '-h has the top priority among valid options' do
+      expect { cli.run(args('-b -v -h')) }.to output(/Usage:/).to_stdout
+      expect { cli.run(args('-b -h -v')) }.to output(/Usage:/).to_stdout
+      expect { cli.run(args('-h -b -v')) }.to output(/Usage:/).to_stdout
+    end
+
+    it '-v has a second from the top priority among valid options' do
+      expect { cli.run(args('-v -h')) }.to output(/Usage:/).to_stdout
+      expect { cli.run(args('-v -b')) }.to output(/knapsack_solver #{KnapsackSolver::VERSION}/).to_stdout
+    end
+
+    it 'at least one method of solving must be selected' do
+      Dir.mktmpdir() do |tmpdir|
+        expect { cli.run(args()) }.to raise_error(/At least one method of solving must be requested/)
+        expect { cli.run(args_in_dataset_out_file('-b', tmpdir)) }.not_to raise_error
+      end
+    end
+    
+    it 'FPTAS must have epsilon constant provided' do
+      Dir.mktmpdir() do |tmpdir|
+        expect { cli.run(args_in_dataset_out_file('-f', tmpdir)) }.to raise_error(/Missing FPTAS epsilon constant/)
+        expect { cli.run(args_in_dataset_out_file('-f -e 0.5', tmpdir)) }.not_to raise_error
+      end      
+    end
+
+    it 'FPTAS epsilon constant must be number from range (0,1)' do
+      Dir.mktmpdir() do |tmpdir|
+        expect { cli.run(args_in_dataset_out_file('-f -e asdf', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/)
+        expect { cli.run(args_in_dataset_out_file('-f -e 0.5x', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/)
+        expect { cli.run(args_in_dataset_out_file('-f -e -0.3', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/)
+        expect { cli.run(args_in_dataset_out_file('-f -e 0', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/)
+        expect { cli.run(args_in_dataset_out_file('-f -e 0.01', tmpdir)) }.not_to raise_error
+        expect { cli.run(args_in_dataset_out_file('-f -e 0.99', tmpdir)) }.not_to raise_error
+        expect { cli.run(args_in_dataset_out_file('-f -e 1', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/)
+      end      
+    end
+
+    it 'epsilon constant must not be provided when FPTAS is not selected' do
+      Dir.mktmpdir() do |tmpdir|
+        expect { cli.run(args_in_dataset_out_file('-b -e 0.5', tmpdir)) }.to raise_error(/epsilon constant must not be provided when FPTAS is not selected/)
+        expect { cli.run(args_in_dataset_out_file('-b -f -e 0.5', tmpdir)) }.not_to raise_error
+      end      
+    end
+
+  end
+  
+  context 'positional arguments' do
+    it 'must have at least one dataset provided' do
+      expect { cli.run(args('-b')) }.to raise_error(/Missing datset file\(s\)/)
+    end
+
+    it 'dataset path must be a path to a regular file' do
+      Dir.mktmpdir do |tmpdir|
+        expect { cli.run(args('-b ' + tmpdir)) }.to raise_error(/is not a regular file/)
+      end      
+    end
+
+    it 'dataset file must exist' do
+      Dir.mktmpdir do |tmpdir|
+        not_existent_file = File.join(tmpdir, 'size_4.dataset')
+        expect { cli.run(args('-b ' + not_existent_file)) }.to raise_error(/does not exists/)
+      end      
+    end
+    
+    it 'dataset file must be readable' do
+      Dir.mktmpdir do |tmpdir|
+        FileUtils.cp('test/datasets/size_4.dataset', tmpdir)
+        not_readable_file = File.join(tmpdir, 'size_4.dataset')
+        FileUtils.chmod('a-r', not_readable_file)
+        expect { cli.run(args('-b ' + not_readable_file)) }.to raise_error(/is not readable/)
+      end      
+    end
+
+    it 'dataset file must have correct format' do
+      Dir.mktmpdir do |tmpdir|
+        invalid_files = %w(invalid_1.dataset
+                           invalid_2.dataset
+                           invalid_3.dataset
+                           invalid_4.dataset
+                           invalid_5.dataset
+                           invalid_6.dataset
+                           invalid_7.dataset
+                           invalid_8.dataset)
+        error_messages = ['missing ID',
+                          'first line does not contain ID',
+                          'ID is negative',
+                          'ID is not an integer',
+                          'missing knapsack capacity',
+                          'missing pairs \(price, weight\)',
+                          'instance desctiption contains negative number',
+                          'instance desctiption does not contain only integers']
+        file_list('test/invalid_datasets', invalid_files).each_with_index do |f, i|
+          expect { cli.run(args('-d ' + f)) }.to raise_error(/#{error_messages[i]}/)
+        end
+      end      
+    end
+  end
+  
+  context 'output of results' do
+    it 'directory for the output logs must exist' do
+      Dir.mktmpdir do |tmpdir|
+        not_existent_file = File.join(tmpdir, 'size_4.dataset')
+        expect { cli.run(args('-b -o ' + not_existent_file)) }.to raise_error(/does not exists/)
+      end      
+    end
+
+    it 'path to a directory for the output logs must point to a directory' do
+      Dir.mktmpdir do |tmpdir|
+        FileUtils.cp('test/datasets/size_4.dataset', tmpdir)
+        file = File.join(tmpdir, 'size_4.dataset')
+        expect { cli.run(args('-b -o ' + file)) }.to raise_error(/is not a directory/)
+      end      
+    end
+
+    it 'directory for the output logs must be writable' do
+      Dir.mktmpdir do |tmpdir|
+        not_writable_dir = File.join(tmpdir, 'dir')
+        Dir.mkdir(not_writable_dir)
+        FileUtils.chmod('a-w', not_writable_dir)
+        expect { cli.run(args('-b -o ' + not_writable_dir)) }.to raise_error(/is not writable/)
+      end      
+    end
+
+    it 'directory for the graph files must exist' do
+      Dir.mktmpdir do |tmpdir|
+        not_existent_file = File.join(tmpdir, 'size_4.dataset')
+        expect { cli.run(args('-b -g ' + not_existent_file)) }.to raise_error(/does not exists/)
+      end      
+    end
+
+    it 'path to a directory for the graph files must point to a directory' do
+      Dir.mktmpdir do |tmpdir|
+        FileUtils.cp('test/datasets/size_4.dataset', tmpdir)
+        file = File.join(tmpdir, 'size_4.dataset')
+        expect { cli.run(args('-b -g ' + file)) }.to raise_error(/is not a directory/)
+      end      
+    end
+
+    it 'directory for the graph files must be writable' do
+      Dir.mktmpdir do |tmpdir|
+        not_writable_dir = File.join(tmpdir, 'dir')
+        Dir.mkdir(not_writable_dir)
+        FileUtils.chmod('a-w', not_writable_dir)
+        expect { cli.run(args('-b -g ' + not_writable_dir)) }.to raise_error(/is not writable/)
+      end      
+    end
+
+    it 'writes graph files' do
+      Dir.mktmpdir do |tmpdir|
+        png_files = %w(avg_price.png avg_cpu_time.png avg_wall_clock_time.png avg_relative_error.png)
+        gnuplot_files = %w(avg_price.gnuplot avg_cpu_time.gnuplot avg_wall_clock_time.gnuplot avg_relative_error.gnuplot)
+        files = png_files + gnuplot_files
+        cli.run(args_in_dataset_out_file('-b -g ' + tmpdir, tmpdir))
+        expect(file_list(tmpdir, files)).to all be_a_regular_file
+      end      
+    end
+
+    it 'writes results and stats to files' do
+      Dir.mktmpdir do |tmpdir|
+        results_files = %w(size_4_branch_and_bound.results size_10_branch_and_bound.results)
+        stats_files = %w(size_4_branch_and_bound.stats size_10_branch_and_bound.stats)
+        files = results_files + stats_files
+        cli.run(args_in_dataset_out_file('-b', tmpdir))
+        expect(file_list(tmpdir, files)).to all be_a_regular_file
+      end
+    end
+
+    it 'writes results and stats to stdout' do
+      results_files = %w(size_4_branch_and_bound.results size_10_branch_and_bound.results)
+      stats_files = %w(size_4_branch_and_bound.stats size_10_branch_and_bound.stats)
+      files = results_files + stats_files
+      files.each do |f|
+        expect { cli.run(args('-b test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.to output(/#{f}/).to_stdout
+      end
+    end
+
+    it 'adds relative error if an exact solving method is selected' do
+      expect { cli.run(args('-r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.not_to output(/avg_relative_error/).to_stdout
+      expect { cli.run(args('-f -e 0.5 -r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.not_to output(/avg_relative_error/).to_stdout
+      expect { cli.run(args('-b -r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.to output(/avg_relative_error/).to_stdout
+      expect { cli.run(args('-d -r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.to output(/avg_relative_error/).to_stdout
+    end
+
+    it 'produces correct results' do
+      Dir.mktmpdir do |tmpdir|
+        results_files = %w(size_10_dynamic_programming.results
+                           size_10_fptas.results
+                           size_10_heuristic.results
+                           size_4_dynamic_programming.results
+                           size_4_fptas.results
+                           size_4_heuristic.results)
+        stats_files = %w(size_10_dynamic_programming.stats
+                         size_10_fptas.stats
+                         size_10_heuristic.stats
+                         size_4_dynamic_programming.stats
+                         size_4_fptas.stats
+                         size_4_heuristic.stats)
+        good_results_files = results_files.map { |f| File.join('test/output_logs', f) }
+        good_stats_files = stats_files.map { |f| File.join('test/output_logs', f) }
+        files = results_files + stats_files
+        cli.run(args_in_dataset_out_file('-b -d -r -f -e 0.5', tmpdir))
+        expect(file_list(tmpdir, files)).to all be_a_regular_file
+        expect(file_list(tmpdir, results_files)).to all be_a_valid_results_file
+        expect(file_list(tmpdir, stats_files)).to all be_a_valid_stats_file
+
+        file_list(tmpdir, results_files).each_with_index do |f, i|
+          expect(f).to be_a_equal_to_results_file(good_results_files[i])
+        end
+
+        file_list(tmpdir, stats_files).each_with_index do |f, i|
+          expect(f).to be_a_equal_to_stats_file(good_stats_files[i])
+        end
+      end
+     
+    end
+
+  end
+
+end
diff --git a/test/output_logs/size_10_dynamic_programming.results b/test/output_logs/size_10_dynamic_programming.results
new file mode 100644
index 0000000..62c8189
--- /dev/null
+++ b/test/output_logs/size_10_dynamic_programming.results
@@ -0,0 +1,5 @@
+# ../test/output_logs/size_10_dynamic_programming.results
+# price    config    cpu_time    wall_clock_time    relative_error
+100 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 0.009999999999999981 0.016795745003037155 0.0
+6 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.005632286978652701 0.0
+19 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.011052408022806048 0.0
diff --git a/test/output_logs/size_10_dynamic_programming.stats b/test/output_logs/size_10_dynamic_programming.stats
new file mode 100644
index 0000000..7ec5c52
--- /dev/null
+++ b/test/output_logs/size_10_dynamic_programming.stats
@@ -0,0 +1,3 @@
+# ../test/output_logs/size_10_dynamic_programming.stats
+# avg_price    avg_cpu_time    avg_wall_clock_time    avg_relative_error
+41.666666666666664 0.01 0.011160146668165302 0.0
diff --git a/test/output_logs/size_10_fptas.results b/test/output_logs/size_10_fptas.results
new file mode 100644
index 0000000..154def2
--- /dev/null
+++ b/test/output_logs/size_10_fptas.results
@@ -0,0 +1,5 @@
+# ../test/output_logs/size_10_fptas.results
+# price    config    cpu_time    wall_clock_time    relative_error
+100 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 0.009999999999999981 0.003663021983811632 0.0
+6 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.008500695985276252 0.0
+19 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.013226451963419095 0.0
diff --git a/test/output_logs/size_10_fptas.stats b/test/output_logs/size_10_fptas.stats
new file mode 100644
index 0000000..fdfe485
--- /dev/null
+++ b/test/output_logs/size_10_fptas.stats
@@ -0,0 +1,3 @@
+# ../test/output_logs/size_10_fptas.stats
+# avg_price    avg_cpu_time    avg_wall_clock_time    avg_relative_error
+41.666666666666664 0.01 0.008463389977502326 0.0
diff --git a/test/output_logs/size_10_heuristic.results b/test/output_logs/size_10_heuristic.results
new file mode 100644
index 0000000..7b0058c
--- /dev/null
+++ b/test/output_logs/size_10_heuristic.results
@@ -0,0 +1,5 @@
+# ../test/output_logs/size_10_heuristic.results
+# price    config    cpu_time    wall_clock_time    relative_error
+100 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 0.009999999999999981 0.010833156033186242 0.0
+0 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 0.010000000000000009 0.005375430977437645 1.0
+19 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.02155825894442387 0.0
diff --git a/test/output_logs/size_10_heuristic.stats b/test/output_logs/size_10_heuristic.stats
new file mode 100644
index 0000000..212314f
--- /dev/null
+++ b/test/output_logs/size_10_heuristic.stats
@@ -0,0 +1,3 @@
+# ../test/output_logs/size_10_heuristic.stats
+# avg_price    avg_cpu_time    avg_wall_clock_time    avg_relative_error
+39.666666666666664 0.01 0.012588948651682585 0.3333333333333333
diff --git a/test/output_logs/size_4_dynamic_programming.results b/test/output_logs/size_4_dynamic_programming.results
new file mode 100644
index 0000000..915cf14
--- /dev/null
+++ b/test/output_logs/size_4_dynamic_programming.results
@@ -0,0 +1,5 @@
+# ../test/output_logs/size_4_dynamic_programming.results
+# price    config    cpu_time    wall_clock_time    relative_error
+65 [1, 0, 0, 0] 0.009999999999999995 0.011663347017019987 0.0
+86 [0, 0, 1, 0] 0.010000000000000009 0.006198941962793469 0.0
+52 [0, 0, 1, 0] 0.009999999999999995 0.012558827002067119 0.0
diff --git a/test/output_logs/size_4_dynamic_programming.stats b/test/output_logs/size_4_dynamic_programming.stats
new file mode 100644
index 0000000..fb64352
--- /dev/null
+++ b/test/output_logs/size_4_dynamic_programming.stats
@@ -0,0 +1,3 @@
+# ../test/output_logs/size_4_dynamic_programming.stats
+# avg_price    avg_cpu_time    avg_wall_clock_time    avg_relative_error
+67.66666666666667 0.01 0.010140371993960192 0.0
diff --git a/test/output_logs/size_4_fptas.results b/test/output_logs/size_4_fptas.results
new file mode 100644
index 0000000..e86ea0d
--- /dev/null
+++ b/test/output_logs/size_4_fptas.results
@@ -0,0 +1,5 @@
+# ../test/output_logs/size_4_fptas.results
+# price    config    cpu_time    wall_clock_time    relative_error
+65 [1, 0, 0, 0] 0.009999999999999981 0.006782401964301243 0.0
+86 [0, 0, 1, 0] 0.010000000000000009 0.012463745952118188 0.0
+52 [0, 0, 1, 0] 0.010000000000000009 0.006875811057398096 0.0
diff --git a/test/output_logs/size_4_fptas.stats b/test/output_logs/size_4_fptas.stats
new file mode 100644
index 0000000..185ff93
--- /dev/null
+++ b/test/output_logs/size_4_fptas.stats
@@ -0,0 +1,3 @@
+# ../test/output_logs/size_4_fptas.stats
+# avg_price    avg_cpu_time    avg_wall_clock_time    avg_relative_error
+67.66666666666667 0.01 0.008707319657939175 0.0
diff --git a/test/output_logs/size_4_heuristic.results b/test/output_logs/size_4_heuristic.results
new file mode 100644
index 0000000..67825c4
--- /dev/null
+++ b/test/output_logs/size_4_heuristic.results
@@ -0,0 +1,5 @@
+# ../test/output_logs/size_4_heuristic.results
+# price    config    cpu_time    wall_clock_time    relative_error
+65 [1, 0, 0, 0] 0.009999999999999995 0.0105733550444711 0.0
+86 [0, 0, 1, 0] 0.010000000000000009 0.00713886899757199 0.0
+52 [0, 0, 1, 0] 0.010000000000000009 0.014065870986087248 0.0
diff --git a/test/output_logs/size_4_heuristic.stats b/test/output_logs/size_4_heuristic.stats
new file mode 100644
index 0000000..889433d
--- /dev/null
+++ b/test/output_logs/size_4_heuristic.stats
@@ -0,0 +1,3 @@
+# ../test/output_logs/size_4_heuristic.stats
+# avg_price    avg_cpu_time    avg_wall_clock_time    avg_relative_error
+67.66666666666667 0.010000000000000004 0.010592698342710113 0.0
diff --git a/test/spec_helper.rb b/test/spec_helper.rb
new file mode 100644
index 0000000..adec803
--- /dev/null
+++ b/test/spec_helper.rb
@@ -0,0 +1,5 @@
+RSpec.configure do |c|
+  c.color = true
+  c.formatter = :documentation
+  c.tty = true
+end