01 배낭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import defaultdict

stuff = {2:3, 3:4, 4:8, 5:8, 9:10}

def bag(stuff,w):
    solution_map = defaultdict(int)
    usedlist_map = defaultdict(list)
    for s in range(1, w+1):
        best = s    # 이번 패스에서 최적의 수
        temp = 0    # 이번 패스에서 배낭에 넣을 보석
        for i in [x for x in stuff.keys() if x <= s]:
            # 보석을 중복해서 사용할 수 없는 한도 내에서, 해당 패스에서 최적의 수를 찾는다.
            if (i not in usedlist_map[s-i]) and (solution_map[s-i] + stuff[i] >= best):
                best = solution_map[s-i] + stuff[i] # 최적의 수 갱신
                temp = i                            # 배낭에 넣을 보석 갱신
        # 이번 패스의 결과
        solution_map[s] = best
        usedlist_map[s] = usedlist_map[s-temp] + [temp]
    return solution_map[w]

1
2
3
4
5
6
7
def knapsack(W, n ,weight, value):
  if W == 0 or n == 0:
    return 0
  if weight[n-1] > W:
    return knapsack(W, n-1, weight, value)
  else:
    return max(value[n-1] + knapsack(W-weight[n-1], n-1, weight, value), knapsack(W, n-1, weight, value))