백준 12920 평범한 배낭 2 - C++

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

12920번: 평범한 배낭 2

신촌 알고리즘 캠프 5주차 Problem Solving 파트 필수문제

 

같은 물건을 여러개 가져갈 수 있다는 사실을 제외하면, 0-1 Knapsack 문제와 크게 다르지 않다.

<문제>

이 문제는 아주 평범한 배낭에 관한 두 번째 문제이다.
민호는 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는 물건의 개수이다.

---

<출력>

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

 

 

<접근 방식>

 

처음 문제를 딱 받고는 학교에서 알고리즘 시간에 배운  Max-profit, bound를 사용한 DFS를 이용할 생각이었다.

물론 위의 접근 방식으로 통과했을 수도 있지만 작성 시간도 오래 걸리고, Worst Case에서는 똑같이 O(NMK)가 나와서 실패하지 않았을까 싶다.

 

강의에서 배운 바는 입력으로 주어지는 K개의 물건을 각각 구분이 가능하게 묶어서 구분 가능한 0-1 Knapsack 문제로 바꾸는 아이디어였다. 같은 입력으로 주어지는 K개의 물건을 1, 2, 4, ... 2^m 개 꼴로 묶어서 따로 따로 배치한다면 O(NMK)가 아닌 O(NMlogK)로 시간 복잡도를 압축할 수 있을 것이다. 

 

해당 아이디어는 이 문제 뿐만 아니라 다른 문제들에서도 은근히 자주 나온다고 하니 잘 숙지하자..

 

같은 속성을 가진 여러개 중 몇 개를 선택해야할 때, 여러개를 log 꼴로 바꿔서 쪼개서 각기 다른 속성을 지닌 걸로 치환시킬 수 있다. 

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

// 백준 12920 평범한 배낭 2

// Knapsack 문제
// 물건의 개수, 만족도, 무게가 주어진다.

// 물건의 종류의 개수 <= 100
// 배낭의 최대 무게 <= 10,000, 개수의 최대값 <= 10,000

// DP[x] : 무게가 x일 때, 얻을 수 있는 최대 만족도라고 하고,
// 그냥 DP를 이용하면, 시간 복잡도가 O(NMK)가 나와서 시간 초과

// 가장 핵심적인 아이디어는 K개의 물건을 logK개의 물건으로 
// 정확히 동치조건으로 만들어서 시간 복잡도를 줄이는 것이다. => ???

// 1. K개 물건이 준비되어 있다.
// 2. 1, 2, 4, ... , 2^m 그리고 K+1 - 2^(m+1)  크기의 패키지 물건이 준비되어 있다.
// (같은 물건들을 개수마다 엮어서 새로운 물건으로 취급한다? => 그러면 logK개의 물건 추가로 그냥 DP를 사용 가능)


vector <pair<ll, ll>> a;
ll dp[2000][10101] = {0, };

int main(void){
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    a.push_back({0,0});
    
    ll v, c, k;
     for(int i=0;i<n;i++){
        ll tmp = 1, sum = 0;
        cin >> v >> c >> k;
        while(sum + tmp <= k){
            a.push_back({v*tmp, c*tmp});
            sum += tmp;
            tmp *= 2;
        }
        if(k - sum > 0){
            a.push_back({v * (k - sum), c * (k - sum)});
        }
    }

    int h = a.size();
    for(int i=1;i<h;i++){
        for(int j=0;j<=m;j++){
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            if(j >= a[i].first){
                dp[i][j] = max(dp[i][j], dp[i-1][j - a[i].first] + a[i].second);
            }
        }
    }
    v = 0;
    for(int i=0;i<=m;i++){
        v = max(v, dp[h-1][i]);
    }
    cout << v;

    return 0;
}