Найти элементы, которые суммируются с заданным номером

Question

Мне нужно найти список заказов с суммой суммы заказа, равной или превышающей заданный номер. Например,

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

И если мне нужно найти заказы, в которых сумма сумма заказа равна 300 или больше, чем 300, то я должен получить О5, О6, o2, O7, O3, o1 или o1 , o4, o3. Не имеет значения, является ли порядок минимальным или максимальным или минимальным. Как я могу сделать это в минимальном порядке? Я знаю, что первым шагом будет сортировка. Я могу использовать сумму массива, чтобы получить сумму всех элементов, но как мне получить элементы, которые составляют или просто больше заданного числа?

Я использую Ruby on Rails с Oracle как db.

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 мы 'd закончено: поскольку величины все неотрицательны, мы рассчитали бы наибольшее возможное значение для суммы подмножества величин.

Тогда просто не принимать элементы в отсортированном порядке, пока сумма величин, по меньшей мере, 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