[python] 백준 12920번: 평범한 배낭 2

문제

문제 출처 : https://www.acmicpc.net/problem/12920

이 문제는 아주 평범한 배낭에 관한 두 번째 문제이다.

민호는 BOJ 캠프에 가기 위해 가방을 싸려고 한다. 가방에 어떠한 물건들을 넣냐에 따라 민호의 만족도가 달라진다. 집에 있는 모든 물건들을 넣으면 민호가 느낄 수 있는 만족도는 최대가 될 것이다. 하지만 민호가 들 수 있는 가방의 무게는 정해져 있어 이를 초과해 물건을 넣을수가 없다.

민호가 만족도를 최대로 느낄 수 있는 경우를 찾아보자.

단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다.

입력

첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다.

두 번째 줄부터 N개의 줄에 걸쳐 민호의 집에 있는 물건의 정보가 주어진다.

각각의 줄은 V, C, K (1 ≤ V ≤ M, 1 ≤ C, K ≤ 10,000, 1 ≤ V * K ≤ 10,000) 으로 이루어져 있다.

V는 물건의 무게, C는 물건을 가방에 넣었을 때 올라가는 민호의 만족도, K는 물건의 개수이다.

출력

최대 무게를 넘기지 않게 물건을 담았을 때 민호가 느낄 수 있는 최대 만족도를 출력한다.

문제 풀이

접근

문제 이름부터 평범한 배낭이고 문제를 봐도 냅색 알고리즘인걸 쉽게 알 수 있었다. 하지만 물건의 개수가 1개 또는 무한대가 아니라 정해져 있는점이 어려웠다.
처음에는 3차원 dp테이블을 만들까 고민했지만 딱봐도 메모리가 부족할 것 같았고, 개수만큼 물건을 추가하는 것도 어려울 것 같았다.

풀이

1. 2의 제곱수들의 합으로 물건의 개수를 표현할 수 있다.
2. 예를 들어 물건이 10개가 있으면 (1C, 1V), (2C, 2V), (4C, 4V), (3C, 3V) 으로 1 ~ 10의 개수를 표현할 수 있다.
3. 나머지는 배낭 문제와 똑같다.

코드

n, m = map(int, input().split())
things = []
for _ in range(n):
    weight, value, k = map(int, input().split())

    i = 1
    while k > 0:
        j = min(i, k)
        things.append((weight * j, value * j))
        k -= i
        i *= 2

n = len(things)

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    weight = things[i - 1][0]
    value = things[i - 1][1]
    for j in range(1, m + 1):
        if j < weight:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)

print(dp[n][m])

후기

물건의 개수를 처리하는 방법만 생각해내면 나머지는 그냥 배낭문제라 어렵지는 않은 것 같다. (생각해 내는게 쉽지 않다)