(복습)백준 12865번 (평범한 배낭) - 냅색 알고리즘 - Python3 파이썬

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1 복사

4 7
6 13
4 8
3 6
5 12

예제 출력 1 복사

14

---

정답

## 냅색 알고리즘 ****** ##

N, K = map(int,input().split())
stuff= [[0,0]]
knapsack = [[0 for _ in range(K+1)] for _ in range(N+1)]

print(knapsack)
for _ in range(N):
    stuff.append(list(map(int,input().split())))

for i in range(1,N+1):
    for j in range(1 , K+1):
        weight = stuff[i][0]
        value = stuff[i][1]

        if j < weight:
            knapsack[i][j] = knapsack[i-1][j]
        else:
            knapsack[i][j] = max(value + knapsack[i-1][j-weight], knapsack[i-1][j])

print(knapsack[N][K])



### 흐름도 ###(참고 링크 https://hongcoding.tistory.com/50)
① 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.

② else, 다음 중 더 나은 가치를 선택하여 넣는다

    2-1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다.

    2-2) 현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다

입력