https://www.acmicpc.net/problem/12865

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

# 입력
N, K = map(int, input().split())
W = [0]
V = [0]
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

# dp 초기화
dp = [[0] * (K+1) for _ in range(N + 1)]

# dp[i][wt]:
# i번째 물건까지 가방에 넣을 수 있는 경우,
# 가방 무게가 wt라면 이 때의 가치합의 최대

for i in range(1, N+1):
    for wt in range(1, K+1):
        if wt < W[i]:
            dp[i][wt] = dp[i-1][wt]
        else:
            dp[i][wt] = max(dp[i-1][wt-W[i]] + V[i], dp[i-1][wt])


print(max(map(max, dp)))

---

🧂아이디어

🔼 else부분 오타 수정! dp[i][wt] = max( dp[i-1][wt-w[i]] + v[i], dp[i-1][wt] )

0-1 knapsack problem (선택하지 않거나, 선택하거나)

• dp[i][wt] = i번째 물건까지 가방에 넣을 수 있는 경우, 가방 무게가 wt라면 이때의 가치합의 최대를 저장

• 2가지 케이스

  1. wt < w[i]인 경우

     • 그냥 skip하는 것이 아니라 (i-1)번째까지의 물건을 넣을 수 있을 때 가방 무게가 wt가 되는 최대 가치합으로 갱신해줘야 함.
     • dp[i][wt] = dp[i-1][wt]
     • 처음 제출한 코드에서는 깜빡하고, wt<w[i]인 경우 갱신을 해주지 않아서(초기 값인 0으로 남겨둠) 오답이었다!

  2. wt >= W[i]인 경우

     • i번째 물건을 넣는 경우
       • dp[i-1][wt - w[i]] + v[i]
     • i번째 물건을 넣지 않는 경우
       • dp[i-1][wt]
     • dp[i][wt]는 두 경우의 최대값
       • dp[i][wt] = max( dp[i-1][wt-w[i]] + v[i], dp[i-1][wt] )