백준 12920번 : 평범한 배낭 2 - 냅색 DP

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

12920번: 평범한 배낭 2

1. 문제설명

0-1 냅색알고리즘을 이용하는 문제이다.

이 문제에서는 아이템이 복수개인 경우가 존재한다.

이를 아이템 하나씩 나눠서 기존의 0-1 냅색 알고리즘을 시행하면 아이템 개수가 많아지기 때문에 시간초과가 난다.

 

아이템 개수 여러개를 줄여줄 수 있는 방법이 필요하다.

이진수는 모든 정수를 표현함을 이용하면 문제를 해결할 수 있다.

 

예를 들어 아이템 15개인 경우에는

아이템을 사용할 수 있는 경우의 수는

1, 2, 3, ... 15까지 총 15개가 있다.

 

이를 다른 방법으로 표현할 수 있다.

아이템을 하나씩 두는 게 아니라

아이템 1개, 아이템 2개, 아이템 4개, 아이템 8개로 덩어리를 만들어 새로운 아이템을 만들면

덩어리 4개로 15개를 표현할 수 있다.

 

 

이 문제에 적용하면 만약 무게 3, 만족도 4인 아이템의 개수 K가 10이라 치면

이를 다음과 같은 아이템으로 처리하고 0-1 냅색 알고리즘을 시행하면 된다.

 

일단 K가 10이므로 덩어리를 만들면

1, 2, 4, 3(2의 배수로 더이상 나눠지지 않으면 나머지는 그냥 둔다)으로 만들 수 있고

 

무게 3, 만족도 4,

무게 6, 만족도 8

무게 12, 만족도 16

무게 9, 만족도 12

인 아이템이 4개 있다고 생각하고 냅색 알고리즘을 시행하면

결과적으로 초기에 10개 있던 아이템에 대해서 아이템을 0개쓴경우부터 ~ 10개 다쓴경우가 적용되어

문제를 해결할 수 있다.

 

이렇게 하면 아이템의 총 개수가 log를 씌운 값에 가까워져서 연산을 덜 할 수 있다.

 

 

 

2.문제풀이코드 

#include <bits/stdc++.h>

using namespace std;

int N, M;
int dp[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        int V, C, K;
        cin >> V >> C >> K;

        int cnt = 1;
        while (K > 0) {
            cnt = min(cnt, K);
            for (int j = M; j >= V * cnt; j--) {
                dp[j] = max(dp[j], dp[j - V * cnt] + C * cnt);
            }
            K -= cnt;
            cnt *= 2;
        }
    }
    cout << dp[M] << '\n';

    return 0;
}