백준 12920 평범한 배낭2

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이문제는 평범한 배낭1의 업그레이드(?) 문제입니다. 아마 이문제 푸시는 분들은 평범한 배낭1문제를 푸셨을 거라고 생각하는데요. 두문제의 유일한 차이는 물건의 개수입니다. 이문제 같은 경우 물건의 개수가 여러개 일 수 있습니다. 따라서 각각 경우를 모두 고려해주어야 하는데 어떻게 해야할지 생각이 잘 안나서 다른 분들의 풀이를 참고 하였습니다.

 

가장 중요한 아이디어는 사용할 수 있는 물건의 개수를 2의 제곱수의 합으로 분리 시키는 것입니다.

예를 들어 A라는 물건이 7개 있다면 각각 1개 / 2개 /4개의 물건으로 분리시키고 그에 맞는 만족도를 저장합니다. 이런식으로 분리시키면 각각 1,2,4의 조합으로 1개부터 7개까지 선택하는 모든 조합을 확인할 수 있게 됩니다. 따라서 모든 물건에 대해서 이 과정을 진행해주면 결국 기존의 냅색문제가 됩니다. 따라서 이후에는 평범한 배낭1 에서 풀었던 방식으로 문제를 해결하면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cstring>
#include <vector>

#define MAX 10001
using namespace std;

int V[MAX];
int C[MAX];
int K[MAX];
int dp[MAX];
int N,M;
vector<pair<int, int> > thing;

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        cin >> V[i] >> C[i] >> K[i];
    }


    for(int j = 0; j < N; j++) {
        for(int i = K[j]; i > 0; i>>=1) {
            int num = i-(i>>1);
            thing.push_back({V[j]*num, C[j]*num});
        }
    }

    for(int i = 0; i < thing.size(); i++) {
        int v = thing[i].first;
        int c = thing[i].second;
        for(int j = M; j >= v; j--) {
            dp[j] = max(dp[j], dp[j-v]+c);
        }
    }
    cout<<dp[M];

    return 0;
}