8944 배낭채우기4 (정올, python3)

https://jungol.co.kr/problem/8944

시간 제한	메모리 제한
1초	1024MB

문제

개의 물건 종류가 있으며, 각 물건은 다음 정보를 가진다.

• $W$: 무게
• $C$: 가치
• $K$: 최대 사용 가능 개수

각 물건은 $0$개 이상 $K$개 이하로 선택할 수 있다.
선택한 물건들의 총 무게는 $M$을 초과할 수 없다.

총 무게가 $M$을 넘지 않도록 물건을 선택했을 때, 얻을 수 있는 가치의 최댓값을 구하라.

 

입력

첫 줄에 정수 $N$, $M$이 주어진다.

다음 $N$개의 줄에 정수 $W$, $C$, $K$가 주어진다.

[제약 조건]

• $1 \le N \le 100$
• $1 \le M \le 10\,000$
• $1 \le W \le M$
• $1 \le C \le 10\,000$
• $1 \le K \le 10\,000$
• $W \times K \le 10\,000$

 

출력

조건을 만족하는 최대 가치를 출력한다.

 

---

풀이

간단히 $N$개의 물건에 대해 각각 최대 $K$개로 총 무게 $M$에 대한 최적해를 계속 찾아보면 됩니다. 단순히 3중 for문으로 돌리면 $O(NMK)$로 시간초과입니다. $K$개를 빠르게 처리할 수 있는 방법을 찾아야 합니다. $K$개를 하나하나 확인하는 방법도 있겠지만, 이 문제는 각 물건의 $K$개를 적절히 쪼개 0-1 배낭문제로 바꿔버릴 수 있습니다.

 

만약 23개가 있는 물건이 있다고 해봅시다. 총 24+1번의 순회를 통해 0~24개를 선택하는 방법을 다 확인해볼 수 있지만 이진분할을 통해 5개의 짐으로 바꿔버려서 5번만 확인하면 끝나게 만들 수 있습니다. 즉, 시간 복잡도를 $O(NMlogK)$로 개선할 수 있습니다.

 

24개의 짐은 `1개` / `2개` / `4개` / `8개` / `9개` 의 짐으로 나눌 수 있습니다. 이 5개로 나뉜 짐을 적절히 선택하는 것으로 0~24개의 를 선택하는 모든 방법을 다 확인할 수 있습니다.

 

 

정답 코드

def solution():
    n, m = map(int, input().split())
    dp = [0] * (m+1)
    for i in range(1, n+1):
        w, c, k = map(int, input().split())
        bit = 1
        while k:
            if bit > k: bit = k
            nc, nw = c*bit, w*bit
            k -= bit
            bit <<= 1
            if nw > m: continue

            for j in range(m, nw-1, -1):
                dp[j] = max(dp[j-nw]+nc, dp[j])

    print(dp[m])

solution()