查找总和为给定数字的元素

Question

我必须找到订单金额总和等于或大于给定数字的订单列表。例如，

order #  amount
o1        100
o2         50
o3         90
o4        150
o5        20
o6        30
o7        50

而如果我需要查找订单金额总和等于300或大于300的订单，那么我应该得到o5、o6、o2、o7、o3、o1或o1、o4、o3。顺序是从最小值到最大值还是从最大值到最小值并不重要。我怎样才能以最少的方式做到这一点？我知道第一步是排序。我可以使用数组求和来获取所有元素的总和，但如何获取加起来等于或大于给定数字的元素？

我在 Rails 上使用 Ruby，Oracle 作为数据库。

Answer 1

你的问题其实很简单。首先，按数量递减排序：

orders = [["o1", 100], ["o2", 50], ["o3", 90], ["o4", 150],
          ["o5",  20], ["o6", 30], ["o7", 50]] 

sorted_orders = orders.sort_by(&:last).reverse
  #=> [["o4", 150], ["o1", 100], ["o3", 90], ["o7", 50],
  #    ["o2", 50],  ["o6", 30],  ["o5", 20]]

假设：

min_req = 300

先看看是否可以min_req使用所有的项目:

orders.reduce(0) { |tot,(_,qty)| tot+qty } < min_req
  #=> false

如果返回 true 我们就完成了：因为数量都是非负的，我们会计算数量子集总和的最大可能值。

然后简单地按照排序的顺序取出项目，直到数量总和至少为 min_req:

tot = 0
sorted_orders.take_while { |_,qty| tot < min_req && tot += qty }
  #=> [["o4", 150], ["o1", 100], ["o3", 90]]

我们可以将其包装在一个方法中：

def smallest_combination(orders, min_req)
  return nil if orders.reduce(0) { |tot,(_,qty)| tot+qty } < min_req
  tot = 0
  orders.sort_by(&:last)
        .reverse
        .take_while { |_,qty| tot < min_req && tot += qty }
end

smallest_combination(orders, 300)
  #=> [["o4", 150], ["o1", 100], ["o3", 90]] 
smallest_combination(orders, 400)
  #=> [["o4", 150], ["o1", 100], ["o3", 90], ["o7", 50], ["o2", 50]] 
smallest_combination(orders, 500)
  #=> nil

查找总和为给定数字的元素

Find elements that sum to a given number

ruby

arrays

ruby-on-rails

subset-sum