PACKING

출처: 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2권

AOJ PACKING

 

SOL)

 

DP

 

물건을 가지고 갈 경우 안가지고 경우 2가지로 나뉜다.
pack(capacity, item)는 공간이 capacity만큼 있을때 해당 item부터 마지막 item까지
고려하여 가장 큰 만족도를 얻는다.

따라서

가져가지 않는 경우 pack(capacity, item + 1);

가져가는 경우 pack(capacity – info[item].Vol, item + 1) + info[item].Wish

 

가져간 물건을 역추적하는 방법

if pack(capacity, item) = pack(capacity, item +１)이라는 말은
위에서 언급한 대로 가장 큰 만족도를 얻는데 item을 가져가지 않았다는 말은
가져갈 수 있는 부피가 하나도 줄지 않았다는 말이고 따라서 다음 item, 즉 item+1
부터 고려하는 값과 같다는 말이다. 이는 해당 물건을 선택하지 않았다는 말과 같다.

 

else 해당 물건을 선택했으므로 결과에 추가

 

[-] Collapse

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define Vol second.first
#define Wish second.second
#define Name first
int N, V;
int cache[1001][101];
vector<pair<string, pair<int, int> > >info;
vector<string> ans;
int pack(int capacity, int item){
    if (item == N) return 0;
    int& ret = cache[capacity][item];
    if (ret != -1) return ret;
    ret = pack(capacity, item + 1);
    if (capacity >= info[item].Vol)
        ret = max(ret, pack(capacity - info[item].Vol, item + 1) + info[item].Wish);
    return ret;
}
void reconstruct(int capacity, int item, vector<string>&picked){
    if (item == N) return;
    //item이 선택되지 않았다면 true //해당 item이 선택되지 않아도 최대의 만족도를 얻을수이으므로
    if (pack(capacity, item) == pack(capacity, item + 1)){
        reconstruct(capacity, item + 1, picked);
    }
    //선택되었다면 추가
    else{
        picked.push_back(info[item].Name);
        reconstruct(capacity - info[item].Vol, item + 1, picked);
    }
}
int main(){
    freopen("input.txt", "r", stdin);
    int T; cin >> T;
    while (T--) {
        memset(cache, -1, sizeof(cache));
        cin >> N >> V;
        info = vector<pair<string, pair<int, int> > >(N);
        ans.clear();
        for (int i = 0; i < N; i++)
            cin >> info[i].Name >> info[i].Vol >> info[i].Wish;

        reconstruct(V, 0, ans);

        cout << pack(V, 0) << " " << ans.size() << endl;
        for (int i = 0; i < ans.size(); i++)
            cout << ans[i] << endl;
    }

    return 0;
}