금고털이

 

* items의 value가 높은것 부터 채워 넣어야 함

* 같은 value는 합침

 

 

* 합치고 sort하면 sort 시간이 감소함

* 혹은 최대 value 개수의 table을 만들고 value에 각 weight들을 합(이것 자체를 sorted array로 사용)

 

W, N = 100, 2   # capacity, num items
items = [
    [90, 1],    # weight, value
    [70, 2]
]

weight_sums = collections.defaultdict(int)
for w, v in items:
    weight_sums[v] += w

weight_sums = sorted(weight_sums.items(), key=lambda p: p[0], reverse=True)
tot = 0

for v, w in weight_sums:
    if W >= w:
        W -= w
        tot += v*w
    else:
        tot += v*W
        W = 0
        break

print(tot)