algospot - packing

//algospot - packing
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, W;
vector<string> name;
vector<int> vol;
vector<int> pre;
vector<vector<int>> cache;
vector<int> list;
int num;
 
void init()
{
    list = vector<int>();
    num = 0;
    cin >> N >> W;
    name = vector<string>(N);
    vol = pre = vector<int>(N);
    for (int i = 0; i < N; ++i)
        cin >> name[i] >> vol[i] >> pre[i];
    cache = vector<vector<int>>(N, vector<int>(W + 1, -1));
}
 
int dp(int idx, int capa)
{
    if (idx == N)
        return 0;
 
    int &ret = cache[idx][capa];
    if (ret != -1)
        return ret;
    ret = dp(idx + 1, capa);
    if (capa >= vol[idx])
        ret = max(ret, dp(idx + 1, capa - vol[idx]) + pre[idx]);
    return ret;
}
 
void reconstruct(int idx, int capa)
{
    int t = cache[idx][capa];
    if (idx == N - 1)
    {
        if (t)
            list.push_back(idx);
        return;
    }
 
    if (cache[idx + 1][capa] == t)
        reconstruct(idx + 1, capa);
    else
    {
        list.push_back(idx);
        reconstruct(idx + 1, capa - vol[idx]);
    }
}
 
int main()
{
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        cout << dp(0, W) << " ";
        reconstruct(0, W);
        cout << list.size() << "\n";
        for(int i = 0; i<list.size(); ++i)
            cout << name[list[i]] << "\n";
    }
}

 

 

 

 

 

 

https://algospot.com/judge/problem/read/PACKING

algospot.com :: PACKING

 

 

 

 

 

 

PACKING

DP 실제 답 구하는 문제

reconstruct() 재귀함수를 만들어 추적해줍니다!