백준 12920 평범한 배낭 2, 파이썬, 냅색 알고리즘, 비트 마스크

이 문제는 kt cloud 코딩 테스트에 나왔던 문제 중 하나다. 물론 그때는 냅색 알고리즘을 몰라 해결하지 못했었지만...

기존의 평범한 배낭 1 문제 + 비트 마스크 개념까지 더한 난이도가 있는 문제다.

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

코드

N, M = map(int, input().split())

arr = []
d = [0 for _ in range(M + 1)]

for _ in range(N):
    W, C, K = map(int, input().split())

    # 비트 마스크 개념 도입 
    i = 1
    while K > 0:
        m = min(i, K)
        arr.append((W * m, C * m))
        K -= i
        i *= 2

for W, C in arr:
    for i in range(M, W - 1, -1):
        d[i] = max(d[i], d[i - W] + C)

print(d[M])