资源高效地找到一种可能的数字组合以达到给定的总和

Question

我在 Ruby 中使用这些算法：

  def subset_sum(inp, s)
        arr = []
        loop.with_index{|_, i| arr << inp.combination(i+1).to_a.find{
    |c| (c.inject(0) {|sum,x| sum + x})  == s}; break if !a.none? || i == inp.count }
    arr
  end

  subset_sum([1,2,3,4,5,6], 15)

和

  def subset_sum(*args)
    args[0].length.downto(1).flat_map do |i|
      args[0].combination(i).to_a
    end.select do |a|
      a.inject(:+) == args[1]
    end
  end
  
  subset_sum([1,2,3,4,5,6], 15).first

不幸的是，这两条路径都是资源密集型的。如果我增加传入数组，计算需要很长时间。告诉我，是否有解决此问题的最佳 Ruby 方法？

Answer 1

def find_one_subset_sum(inp, sum)
  candidates = inp.filter { |i| i < sum } # don't do this optimize if inp contain negative numbers
  sum_combi_hash = Hash.new do |hash, key|
    if key > 0
      hash[key] = {candidates[key] => [candidates[key]]}
      if hash[key - 1][sum].nil?
        hash[key - 1].each do |s, c|
          hash[key][s] = c
          new_s = s + candidates[key]
          next unless hash[key][new_s].nil?
          hash[key][new_s] = c + [candidates[key]]
          break if new_s == sum
        end
      else
        hash[key][sum] = hash[key - 1][sum]
      end
      hash[key]
    else
      hash[key] = {candidates.first => [candidates.first]}
    end
  end
  sum_combi_hash[candidates.size - 1][sum]
end

Answer 2

我知道数组的所有元素都是非负的。

尝试以下递归。

def subset_sum((first, *rest), target)
  return (first == target ? [first] : nil) if rest.empty?
  rv = subset_sum(rest, target)
  return rv unless rv.nil?
  return nil if first > target
  return [first] if first == target
  rv = subset_sum(rest, target-first)
  rv.nil? ? nil : [first, *rv]
end

arr = [1,2,3,4,5,6]
subset_sum([1,2,3,4,5,6], 15)
  #=> [4,5,6]
arr1 = arr.shuffle
  #=> [5, 3, 6, 4, 2, 1]
subset_sum(arr1, 15)
  #=> [3, 6, 4, 2]
subset_sum([1, 1, 1, 1, 1, 2, 2, 5, 5, 5, 5, 5, 10], 6)
  #=> [1, 5]

在第一个示例中，解决方案很快就找到了，但这只是因为数组的最后三个元素总和为 11。相比之下，当 arr 的元素被打乱以产生 arr1 时，执行时间要长得多。

为了看看发生了什么，让我们添加一些 puts 语句。

def subset_sum((first, *rest), target)
  puts "first = #{first}, rest = #{rest}, target = #{target}"
  if rest.empty?
    puts "  rest is empty, return #{first == target ? [first] : nil}"        
    return first == target ? [first] : nil
  end 
  rv = subset_sum(rest, target)
  puts "  rv #{first} not used"
  puts "  return #{rv}" unless rv.nil?
  return rv unless rv.nil?
  return nil if first > target
  return [first] if first == target
  rv = subset_sum(rest, target-first)
  rv.nil? ? nil : [first, *rv]
end

subset_sum(arr1, 15)
first = 5, rest = [3, 6, 4, 2, 1], target = 15
first = 3, rest = [6, 4, 2, 1], target = 15
first = 6, rest = [4, 2, 1], target = 15
first = 4, rest = [2, 1], target = 15
first = 2, rest = [1], target = 15
first = 1, rest = [], target = 15
  rest is empty, return 
  rv 2 not used
first = 1, rest = [], target = 13
  rest is empty, return 
  rv 4 not used
first = 2, rest = [1], target = 11
first = 1, rest = [], target = 11
  rest is empty, return 
  rv 2 not used
first = 1, rest = [], target = 9
  rest is empty, return 
  rv 6 not used
first = 4, rest = [2, 1], target = 9
first = 2, rest = [1], target = 9
first = 1, rest = [], target = 9
  rest is empty, return 
  rv 2 not used
first = 1, rest = [], target = 7
  rest is empty, return 
  rv 4 not used
first = 2, rest = [1], target = 5
first = 1, rest = [], target = 5
  rest is empty, return 
  rv 2 not used
first = 1, rest = [], target = 3
  rest is empty, return 
  rv 3 not used
first = 6, rest = [4, 2, 1], target = 12
first = 4, rest = [2, 1], target = 12
first = 2, rest = [1], target = 12
first = 1, rest = [], target = 12
  rest is empty, return 
  rv 2 not used
first = 1, rest = [], target = 10
  rest is empty, return 
  rv 4 not used
first = 2, rest = [1], target = 8
first = 1, rest = [], target = 8
  rest is empty, return 
  rv 2 not used
first = 1, rest = [], target = 6
  rest is empty, return 
  rv 6 not used
first = 4, rest = [2, 1], target = 6
first = 2, rest = [1], target = 6
first = 1, rest = [], target = 6
  rest is empty, return 
  rv 2 not used
first = 1, rest = [], target = 4
  rest is empty, return 
  rv 4 not used
first = 2, rest = [1], target = 2
first = 1, rest = [], target = 2
  rest is empty, return 
  rv 2 not used
  rv 5 not used
  return [3, 6, 4, 2]
#=> [3, 6, 4, 2]

总的来说，我不确定这会比使用 Array#combination 快得多，但可以做一些基准测试。

使用动态规划可以获得进一步的改进。状态变量将是数组前 n 个元素中使用的变量的总和。例如，如果前四个元素是

a4 = [1,2,3,4]

那么 1 到 4 个元素的所有组合将是：

all = (1..4).each_with_object([]) do |n,a|
  a4.combination(n).each { |aa| a << aa.sum }
end
  #=> [1, 2, 3, 4, 3, 4, 5, 5, 6, 7, 6, 7, 8, 9, 10]

前 4 个元素的状态变量的可能值将是此数组的唯一值：

all_uniq = all.uniq
  #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

并且如果已知数组的值都是非负的，并且如果目标值是，比如说，6，则该状态变量的可能值将限于以下。

all.uniq.select { |a| a <= 5 }
  #=> [1, 2, 3, 4, 5]

这会很有效地完成，a4 的计算是从 a3 的结果中得出的，依此类推。

如果需要，我可以展示如何编写动态规划解决方案。

资源高效地找到一种可能的数字组合以达到给定的总和

Resource-efficient finding ONE possible combinations of numbers to reach a given sum

ruby

dynamic-programming