diff options
Diffstat (limited to 'lib/knapsack_solver')
| -rw-r--r-- | lib/knapsack_solver/cli.rb | 49 | ||||
| -rw-r--r-- | lib/knapsack_solver/cli_option_checker.rb | 83 | ||||
| -rw-r--r-- | lib/knapsack_solver/cli_option_parser.rb | 68 | ||||
| -rw-r--r-- | lib/knapsack_solver/dataset.rb | 44 | ||||
| -rw-r--r-- | lib/knapsack_solver/graph_printer.rb | 115 | ||||
| -rw-r--r-- | lib/knapsack_solver/instance.rb | 48 | ||||
| -rw-r--r-- | lib/knapsack_solver/output_printer.rb | 97 | ||||
| -rw-r--r-- | lib/knapsack_solver/solver.rb | 118 | ||||
| -rw-r--r-- | lib/knapsack_solver/solving_methods/branch_and_bound.rb | 111 | ||||
| -rw-r--r-- | lib/knapsack_solver/solving_methods/dynamic_programming.rb | 116 | ||||
| -rw-r--r-- | lib/knapsack_solver/solving_methods/fptas.rb | 47 | ||||
| -rw-r--r-- | lib/knapsack_solver/solving_methods/heuristic_price_weight.rb | 56 | ||||
| -rw-r--r-- | lib/knapsack_solver/version.rb | 5 |
13 files changed, 957 insertions, 0 deletions
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 |