PACKING (중, p. 281)

어떻게 풀었나?#

전형적인 Knapsack문제에 답을 역추적 해야하는 부분이 추가된 문제

상태 공간의 정의 dp[v][x] ⇒ items[x]까지 고려하고 부피 v까지 사용할 때 최대의 절박도(d)
점화식 dp[v][x] = max(dp[v][x-1], dp[v - items[x].v][x-1] + items[x].d)
답 역추적 하는 방식 dp[v][x] == dp[v][x-1]이면, items[x]를 고르지 않은 것. dp[v][x] ≠ dp[v][x-1]이면, items[x]를 골랐으므로 items[x]를 답 list에 추가하고, dp[v - items[x].v][x-1]에 대해서 지금과 같은 방식으로 items[x-1]을 골랐는지 다시 확인해보면 됨.

점화식까지는 잘 세웠는데, 답 역추적 할 때 p[현재까지 고른 아이템들의 절박도 합][x] = 이전에 고른 item index 방식으로 접근했다가 계속 RTE맞음. 이유를 계속 모르겠어서 ChatGPT에 물어보니 절박도 합 Max가 100,000이어서 그런 것이었음. (p[1001][101]로 잡았었음) p배열을 매 테케마다 초기화해야 하므로 [100001][101]로 잡을 수 없음 → 이건 애초에 틀린 방법이었음.

이미 이 상태로 3시간이 지난 뒤라, 책을 보고 답 역추적 하는 방식을 적용함.

문제#

정답 코드#

#include <bits/stdc++.h>
using namespace std;
struct Item{
    string name;
    int v,d; //부피, 절박도
    Item(){}
    Item(const string & name, int v, int d):name(name),v(v),d(d) {}
};
vector<Item> items;
const int INF = 0x3f3f3f3f;
int dp[1001][101];
int chk[1001][101];
int CHKVAL;
int f(int v, int x) { // 부피 v만큼 item들을 골라서 최대 절박도 구하기
    if(v<0) return -INF;
    if(x<0) return 0;
    if(chk[v][x] == CHKVAL) return dp[v][x];
    chk[v][x] = CHKVAL;
    int & ret = dp[v][x];

    return ret=max(f(v,x-1), f(v-items[x].v, x-1) + items[x].d);
}
void g(int v, int x, vector<int> & ans) { // 답 역추적하기
    if(x<0) return;
    if(f(v,x) == f(v,x-1)) {
        g(v,x-1,ans);
    }
    else {
        ans.push_back(x);
        g(v-items[x].v,x-1,ans);
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    string name;
    int v,d;
    while(tc--) {
        int N,W; cin >> N >> W;
        items.clear();
        CHKVAL++;
        for(int i=0; i<N; i++) {
            cin >> name >> v >> d;
            items.emplace_back(name,v,d);
        }
        printf("%d ", f(W,N-1));

        static vector<int> ans;
        ans.clear();
        g(W,N-1,ans);
        printf("%lu\n", ans.size());
        for(int i=0; i<ans.size(); i++) {
            printf("%s\n", items[ans[i]].name.c_str());
        }
    }
    return 0;
}