Python：查找数组总和

Question

这个任务对我来说确实很难。 我的任务是找出Sarah可以达到的最高幸福，因为她的包包容量和可供出售的物品。 莎拉携带的包最多可携带3件物品，总重量不超过w kg。 Sarah购买的所有物品必须同时装入她的包里。 例如： w = 97 items = [[17, 19], [22, 19], [65, 64], [21, 19], [27, 26], [19, 21], [58, 61], [43, 46], [1, 3], [44, 42], [22, 22], [52, 53], [10, 8], [37, 35], [60, 62], [42, 39], [36, 36], [62, 60], [50, 47], [62, 62], [47, 48], [15, 16], [12, 12], [6, 5], [30, 27], [52, 49], [30, 32], [3, 4], [21, 18], [58, 58], [43, 42], [50, 50], [41, 41], [60, 60], [55, 58], [64, 63], [32, 33], [11, 12], [11, 13], [46, 44], [22, 21], [20, 19], [47, 45], [24, 24], [35, 32], [28, 31], [14, 15], [35, 37], [9, 10], [23, 22], [45, 46], [34, 32], [34, 37], [37, 39], [42, 41], [59, 57], [24, 22], [15, 13], [33, 34], [3, 3], [55, 55]] 第一个数字是物品的重量。 第二个数字是项目的幸福值。 任何人有任何想法如何计算？

Answer 1

我得到105幸福，物品[11, 13], [28, 31], [58, 61]和[28, 31], [34, 37], [35, 37]使用所有可能的97重量和所有3个累积插槽。

# this allows for integers to be divided by integers and give a float result 
# program is runnable in both python 2 and 3 
from __future__ import division 
from sys import exit 
weight = 97 
items = [[17, 19], [22, 19], [65, 64], [21, 19], [27, 26], [19, 21], [58, 61], 
[43, 46], [1, 3], [44, 42], [22, 22], [52, 53], [10, 8], [37, 35], [60, 62], 
[42, 39], [36, 36], [62, 60], [50, 47], [62, 62], [47, 48], [15, 16], [12, 12], 
[6, 5], [30, 27], [52, 49], [30, 32], [3, 4], [21, 18], [58, 58], [43, 42], 
[50, 50], [41, 41], [60, 60], [55, 58], [64, 63], [32, 33], [11, 12], [11, 13], 
[46, 44], [22, 21], [20, 19], [47, 45], [24, 24], [35, 32], [28, 31], [14, 15], 
[35, 37], [9, 10], [23, 22], [45, 46], [34, 32], [34, 37], [37, 39], [42, 41], 
[59, 57], [24, 22], [15, 13], [33, 34], [3, 3], [55, 55]] 

# this is about half of the problem: we must sort the items by the priority 
# which which we want them. this would be their happiness to weight ratio 
sorted_items = sorted(items, key=lambda item: item[1]/item[0], reverse=True) 

happiness = int() 
for item1 in range(len(sorted_items) - 2): 
    for item3 in range(item1 + 2, len(sorted_items)): 
     for item2 in range(item1 + 1, item3): 
      # try to use as much weight as possible, we don't want 
      # our bag to go underfilled with 3 efficient but light items 
      if (sorted_items[item1][0] + 
       sorted_items[item2][0] + 
       sorted_items[item3][0] <= weight): 
       # we haven't gone over weight! possible solution found! 
       happiness = max(sorted_items[item1][1] + 
           sorted_items[item2][1] + 
           sorted_items[item3][1], happiness) 

print(happiness) 

Answer 2

这是0/1 knapsack problem。最优雅的解决方案是动态编程。你可以找到关于它的讲座here，以及解决方案here。

我建议看看演讲，并尝试在查看解决方案之前自行编码。