Python：查找數組總和

-7

這個任務對我來說確實很難。我的任務是找出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]] 第一個數字是物品的重量。第二個數字是項目的幸福值。任何人有任何想法如何計算？Python：查找數組總和

來源

2014-09-27 Pheng-Khai Tan

考慮到這是功課，你不應該真的試圖弄清楚，並在過程中學習的東西？ – isedev 2014-09-27 07:32:26

@isedev這太苛刻了：也許Pheng-Khai Tan有一個叫Sarah的朋友，他帶着一個可以容納最多三件總重量* w * kg的袋子，並帶有一個易於測量的快樂值。 – Veedrac 2014-09-27 07:36:27

@ Pheng-KhaiTan我建議買一個揹包。但嚴重的是，我建議你閱讀[我如何問及回答作業問題？]（http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions）。 – Veedrac 2014-09-27 07:41:56

-3

我得到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)

來源

2014-09-27 08:58:27 BUSY

這給出了錯誤的結果，這是105幸福。 – Veedrac 2014-09-27 09:28:08

@Veedrac是的，我看到有兩個3項組合，導致105.我會嘗試清除我的解決方案，並表明。謝謝！ – BUSY 2014-09-27 09:32:05

我建議你查看'itertools.combinations'。第二個片段對於您剛剛可以緩存的信息也有很多工作。最後，這也是錯誤的，因爲不能保證權重的總和等於權重限制。 – Veedrac 2014-09-27 09:44:51

這是0/1 knapsack problem。最優雅的解決方案是動態編程。你可以找到關於它的講座here，以及解決方案here。

我建議看看演講，並嘗試在查看解決方案之前自行編碼。

來源

2014-09-27 09:04:39 Korem

Python：查找數組總和

回答

相關問題