(Python)[백준] 평범한 배낭_12865

12865번: 평범한 배낭

• 현재 허용 무게에서 최대 가치를 dp 테이블에 저장해 나감
• 현재 물건을 넣었을 때와 넣지 않았을 때를 비교하여 큰 값을 dp 테이블에 저장
  • 현재 물건을 넣었을 때를 보려면 현재의 허용 무게에서 현재 물건의 무게를 빼야함. 현재의 허용 무게에서 현재 물건의 무게를 뺐을 때의 최대 가치는 dp 테이블에 저장되어 있으므로 그 최대 가치를 찾아감
    1. 아래 그림 예시에서, 3의 무게를 가진 물건을 넣기 위해 현재 허용 무게인 7에서 3을 뺌 → 7-3 = 4
    2. 허용 무게가 4일 때의 최대 가치를 찾아감 → (2, 4)
    3. 허용 무게 4에서 현재 물건을 넣었을 때의 값과, 현재 허용 무게인 7에 있던 값을 비교함 → 8+6 vs. 13

풀이

---

# knapsack[i][j] = max(현재 물건 가치 + knapsack[이전 물건][현재 가방 무게 - 현재 물건 무게], knapsack[이전 물건][현재 가방 무게])
# knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

import sys
input = sys.stdin.readline

# 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K
N, K = map(int,input().split())

items = [[0,0]]
knapsack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

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

for i in range(1, N + 1):
    for j in range(1, K + 1):
        weight = items[i][0] 
        value = items[i][1]
       
        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j] # weight보다 작으면 위의 값을 그대로 가져온다
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

print(knapsack[N][K])