파이썬 : 배열의 합계를 찾으십시오.

Question

이 작업은 실제로 꽤 어렵습니다. 나의 임무는 Sarah가 자신의 가방 용량과 판매 가능한 품목을 고려할 때 얻을 수있는 최고의 행복을 찾아내는 것입니다. 새라는 총 무게가 최대 wkg 인 물품을 최대 3 개까지 운반 할 수있는 가방을 소지하고 있습니다. 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

나는 가능한 97 개의 무게와 모든 3 개의 방해물 슬롯을 사용하여 [11, 13], [28, 31], [58, 61] 및 [28, 31], [34, 37], [35, 37] 아이템을 사용하여 105 가지 행복을 얻습니다.

# 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입니다.

나는 해결책을보기 전에 강의를보고 코드를 작성하는 것이 좋습니다.