[백준] 12865번: 평범한 배낭

💻 문제 - G5

✏️0-1 Knapsack

최적의 원리: 어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.

• P[i, w]는 i개의 보석이 있고 배낭의 무게의 한도가 w일 때 최적의 이익이다.
• 즉, 2차원 리스트로 DP를 하는 문제이다.

👉 제출 코드

# wt: 각 보석의 무게, val: 각 보석의 가격
def knapsack(n, W, wt, val):
    P = [[0] * (W+1) for _ in range(n+1)]
    # 시간 복잡도: O(nW)
    for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i] > w:
                P[i][w] = P[i-1][w]
            else:
                P[i][w] = max(val[i] + P[i-1][w-wt[i]], P[i-1][w])
    return P[n][W]

n, k = map(int, input().split())
wt = [0]
val = [0]
for _ in range(n):
    w, v = map(int, input().split())
    wt.append(w)
    val.append(v)
print(knapsack(n, k, wt, val))

• 참고