如何从数组中获得优化选择

我有几个哈希数组（假设我有三个）如下：

a = [{ cost: 10, value: 20}, { cost: 9, value: 20}, { cost: 10, value: 22}, { cost: 2, value: 10} ] b = [{ cost: 4, value: 20}, { cost: 9, value: 20}, { cost: 15, value: 22}, { cost: 12, value: 10} ] c = [{ cost: 10, value: 21}, { cost: 9, value: 20}, { cost: 10, value: 22}, { cost: 3, value: 10} ] 

我需要找出哪个哈希选择，每个数组中的一个，给出了最大总和:value保持总和的:value :cost在给定值下（比方说30 ）。

答案对于这种情况来说可能很容易看到它，但这只是样本数据，实际上我有更多的数组。 有人可以帮助我或指出我正确的方向吗？

编辑：我还要提一下，我想用这个对象数组做。 我以哈希为例，因为它更容易描述，但我打算使用Objects。 此外，如果从一个数组中使用了一个Object，我希望它与其他数组中不使用相同的选项，因此每个选定的Object应该是唯一的。

Answer 1

这是一个单行：

 a.product(b,c).select{ |arr| arr.reduce(0) { |sum,h| sum + h[:cost] } < 30 }.max_by{ |arr| arr.reduce(0){ |sum,h| sum + h[:value]} } 

分手了一点：

 a.product(b,c) .select{ |arr| arr.reduce(0) { |sum,h| sum + h[:cost] } < 30 } .max_by{ |arr| arr.reduce(0) { |sum,h| sum + h[:value] } } 

Answer 2

这将是：

 def find_max_option(max_cost, *arys) a = arys.shift a.product(*arys).map do |c| [ c, c.inject({}) {|result, hash| result.merge(hash) {|_,o,n| o + n } } ] end.select {|_,v| v[:cost] < max_cost}.max_by {|_,v| v[:value]}.first end find_max_option(30, a, b, c) #=> [{:cost=>10, :value=>22}, {:cost=>4, :value=>20}, {:cost=>10, :value=>22}] 

---

由sawa编辑为了便于阅读略微重写。

 def find_max_option(max_cost, *a) a.first.product(*a.drop(1)) .group_by{|hs| hs.inject({}){|acc, h| acc.merge(h){|_, v_acc, v_h| v_acc + v_h}}} .select{|k, _| k[:cost] < max_cost} .max_by{|k, _| k[:value]} .last.first end 

Answer 3

我们可以使用动态编程来有效地为任意数量的数组（散列）解决这个“背包问题”。 解决方案时间大致与arrays数量和平均arrays大小的平方成正比。

我的第一个想法是对此进行编码，但随后决定这将花费太长时间，并且可能不是解释算法如何工作的最佳方式。 相反，我决定展示如何针对问题中给出的示例计算最优解。 应该明白如何为任意数量的arrays实现该算法。

[编辑：毕竟我决定编码。 我在最后添加了tidE]

首先考虑（“最后”）数组c 。 以下是Excel电子表格中相关信息的屏幕截图。

请注意，我没有在偏移量0 ， { cost: 10, value: 21}包含哈希{ cost: 10, value: 21} 。 那是因为哈希是由偏移2处的那个“domninated”， { cost: 10, value: 22} 。 前者永远不会是首选，因为它们都具有相同的成本，而后者具有更高的价值。

第二个表格显示了对于给定的“剩余预算”（即，在选择了a和b哈希值之后）优先选择哪个哈希值。 请注意，可能的剩余预算范围从3 （arraysc哈希值中的最低成本）到24 （总预算， 30减去选择a和b中具有最小成本的哈希值的成本： 30 - 2 - 4 = 24 ）。

最好用一组哈希来实现它：

 [{budget: 3, value: 10, hash_offset: 3 }, {budget: 4, value: 10, hash_offset: 3 }, ... {budget: 8, value: 10, hash_offset: 3 }, {budget: 9, value: 20, hash_offset: 1 }, {budget: 10, value: 22, hash_offset: 2 }, ... {budget: 10, value: 22, hash_offset: 2 }] 

现在让我们转到arraysb 。

这里我只包含了数组b包含的四个哈希中的两个，因为偏移量为1的哈希， { cost: 9, value: 20 }由偏移0处的哈希主导， { cost: 4, value: 20 }哈希{ cost: 12, value: 10}由{ cost: 4, value: 20}支配。

这里的“可用预算”范围为7到27 。 7提供了在b选择一个散列（在偏移0 ，具有成本4 ）和在c一个（在偏移3 ，具有成本3 ）所需的最小值。 范围的高端27是选择a中的散列（ 30 - 3 ）后可能剩余的最大值。

假设剩余预算（对于数组b和c ）为18 。 如果我们在偏移0处选择散列，我们将从该散列中实现20值，并且具有18-4 18 - 4 => 14的剩余预算用于选择arraysc的散列。 从数组c的表中我们看到我们将在数组c中的偏移2处选择散列，其值为22 。 因此，如果可用预算为18并且我们在arraysb偏移0处选择了散列，那么对于arraysb和c ，具有20 + 22 => 42的（最大）值。

我们现在必须考虑在数组b中的偏移2处选择散列，这将产生值22并且留下18-15 18 - 15 => 3的剩余预算用于选择arraysc的散列。 我们从表中看到数组c ，它将是偏移3处的散列，值为10 。 因此，如果可用预算为18并且我们在数组b偏移2处选择了散列，那么我们将得到数组b和c的（最大）值22 + 10 => 32 。

因此，如果我们对arraysb和c的可用预算为18 ，那么最佳选择是在arraysb中偏移0和arraysc中偏移3处选择散列，总（最大）值为42 。 我在表格中概述了这个选择。

同样的结果适用于18-23范围内的任何剩余预算。 将对每个其他可用预算范围执行类似的计算。 当可用预算为24时，你会发现有一个平局。

我们现在可以转到arraysa 。 （我们差不多完成了。）

我没有在偏移量0处包含散列，因为它由偏移量为2的散列支配。

数组a ， b和c的可用预算为30 ，因此我们不必对此进行调整（即对于第一个数组）。 我们必须考虑以下三种可能性：

• 选择偏移1处的散列来获得值20 ，这使得arraysb和c的剩余预算为30 - 9 => 21 ，其中（从数组b的表中）产生最后两个的最佳值42数组，总值为20 + 42 => 62 。

• 选择偏移量为2的散列值，得到值为22 ，对于数组b和c ，剩下的预算为30 - 10 => 20 ，其中（从数组b的表中）得到最后两个的最佳值42数组，总值为22 + 42 => 64 。

• 选择偏移量为3的哈希值，得到10的值，对于数组b和c ，剩下的预算为30 - 2 => 28 ，其中（从数组b的表中）得到最后两个的最佳值44数组，总值为10 + 44 => 54 。

因此，我们得出结论，通过选择arraysa中偏移2的散列，arraysb中偏移0的散列和arraysc中偏移2处的散列，可以实现最大值64 。

码

 def knapsack(all_costs_and_values, total_budget) costs_and_values = remove_dominated_choices(all_costs_and_values) budget = remaining_budget(costs_and_values, total_budget) solution = optimize(costs_and_values, budget) display_solution(costs_and_values, solution) end 

。

 private def remove_dominated_choices(a) a.map do |f| # f.invert.invert ensures that no two keys have the same value g = f.invert.invert g.each_with_object({}) do |(name,v),h| (h[name] = v) unless g.any? { |_,p| (p[:cost] <= v[:cost] && p[:value] > v[:value]) || (p[:cost] < v[:cost] && p[:value] >= v[:value]) } end end end def remaining_budget(b, tot_budget) mc = min_cost_per_hash(b) b.map.with_index do |h,i| if i.zero? (tot_budget..tot_budget) else (mc[i..-1].reduce(:+)..tot_budget - mc[0..i-1].reduce(:+)) end end end def min_cost_per_hash(arr) arr.map { |h| h.values.min_by { |h| h[:cost] }[:cost] } end 

。

 def optimize(costs_and_values,remaining_budget) solution = Array.new(costs_and_values.size) i = costs_and_values.size-1 g = costs_and_values[i].sort_by { |k,v| -v[:cost] } solution[i] = remaining_budget[i].each_with_object({}) do |rb,h| name, f = g.find { |_,v| v[:cost] <= rb } h[rb] = { name: name, value_onward: f[:value] } end while i > 0 i -= 1 g = costs_and_values[i].sort_by { |k,v| v[:cost] } min_to_leave = remaining_budget[i+1].first solution[i] = remaining_budget[i].each_with_object({}) do |rb,h| best = - Float::INFINITY g.each do |name, v| leave_for_next = rb - v[:cost] break if leave_for_next < min_to_leave candidate = v[:value] + solution[i+1][leave_for_next][:value_onward] if candidate > best best = candidate h[rb] = { name: name, value_onward: candidate } end end end end solution end 

。

 def display_solution(costs_and_values, solution) rv = solution.first.keys.first puts "Optimal value: #{ solution.first[rv][:value_onward] }\n" solution.each_with_index do |h,i| name = h[rv][:name] puts " Best choice for hash #{i}: #{name}" rv -= costs_and_values[i][name][:cost] end end 

例

我将all_costs_and_values的数据结构更改为散列数组，其中键是成本/值对的标签（例如， all_costs_and_values '12'指的是以前的行偏移1处的散列，OP的数组中的列偏移2 ）。 我希望用更有意义的字符串替换标签。

 all_costs_and_values = [{ '00' => { cost: 10, value: 20 }, '01' => { cost: 8, value: 17 }, '02' => { cost: 10, value: 20 }, '03' => { cost: 12, value: 24 } }, { '10' => { cost: 6, value: 16 }, '11' => { cost: 4, value: 14}, '12' => { cost: 6, value: 17 }, '13' => { cost: 5, value: 13 } }, { '20' => { cost: 8, value: 16 }, '21' => { cost: 14, value: 30 }, '22' => { cost: 16, value: 32 }, '23' => { cost: 14, value: 32 } }, { '30' => { cost: 2, value: 4 }, '31' => { cost: 5, value: 9 }, '32' => { cost: 10, value: 16 }, '33' => { cost: 6, value: 8 } }] total_budget = 30 knapsack(all_costs_and_values, total_budget) #=> Optimal value: 70 # Best choice for hash 0: 01 # Best choice for hash 1: 12 # Best choice for hash 2: 23 # Best choice for hash 3: 30 

在计算最优值时，构造了哈希solution的数组：

 solution #=> [{ 30=>{:name=>"01", :value_onward=>70}}, # "01" => { cost: 8, value: 17 } leave 30-8 = 22 #=> {14-15=>{:name=>"11", :value_onward=>34}, #=> 16=>{:name=>"12", :value_onward=>37}, #=> 17-18=>{:name=>"11", :value_onward=>39}, #=> 19=>{:name=>"12", :value_onward=>42}, #=> 20-21=>{:name=>"11", :value_onward=>50}, #=> 22=>{:name=>"12", :value_onward=>53}}, # "12" => { cost: 6, value: 17 } leave 22-6 = 16 #=> {10-12=>{:name=>"20", :value_onward=>20}, #=> 13-15=>{:name=>"20", :value_onward=>25}, #=> 16-18=>{:name=>"23", :value_onward=>36}, # "23" => { cost: 14, value: 32 } leave 16-14 = 2 #=> {2-4=>{:name=>"30", :value_onward=>4}, # "30" => { cost: 2, value: 4 } leave 2-2 = 0 #=> 5-9=>{:name=>"31", :value_onward=>9}, #=> 10=>{:name=>"32", :value_onward=>16}}]