algospot :: PACKING 여행 짐 싸기

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

알고리즘 문제해결전략 1권 p.281

 

가능한 물건의 조합을 하나하나 검사해서, 정해진 무게 제한 안에서 최대 절박도를 내는 물건의 조합을 찾아내는 문제다.

 

 

[내가 헤맨 부분]

- 최대 절박도를 찾는것 까지는 동적 계획법으로 쉽게 떠올릴 수 있는데, 물건들의 이름을 출력하는 부분에서 막혔다.

- memset함수를 잘못 이용해서 몇번이나 틀렸다. 값을 직접 계산해서 3번째 인자에 넣고 있었는데, 그냥 sizeof를 이용하는게 정확하다.

 memset(target, value, sizeof(target))

 

[알고리즘]

* 물건들의 index를 동적계획법에 이용하면 문제가 간단해진다.

* int play(int index, int maxVol) 

이 함수는 특정 index 이후의 아이템들로 maxVol 무게제한에서 최대의 절박도를 계산한다.

이때 경우의 수는

case 1. index아이템은 선택하지 않고 + index 다음의 아이템들로 주어진 무게제한을 채울것인가

case 2.  index아이템을 선택하면서 + index 다음의 아이템들로 나머지 무게제한(주어졌던 무게제한에서 index아이템의 무게를 뺀 값)을 채울것인가

이렇게 나뉜다. 

모든 아이템에 대해 이렇게 2가지 경우를 탐색한다면, 각각 아이템을 가져간다/가져가지 않는다의 모든 경우의수를 탐색하게 된다.

- 기저사건(index == numProduct)

index가 numProduct와 같다면 가능한 모든 경우의 수를 탐색했다는 뜻이다. 

이 경우 더 이상 탐색하지 않으며, 해당 사건을 선택하지 않도록 하기 위해 작은 값인 0을 반환한다.

 

 

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

#include <iostream>
#include <vector>
#include <cstring>
#define FOR(i, ed) for(int i = 0 ; i < ed; i++)

using namespace std;

int tc;
// input
int maxVol;
int numProduct;
string product[100];
int volume[100];
int need[100];
// for process
int cache[1001][100]; // index 이후의 물건들로 maxVol을 채울 때 최대 절박도
vector<string> packed; //마지막에 가방에 담은 아이템들을 저장할 벡터

//cache[maxVol][index]값을 찾아서 반환하는 함수
int play(int index, int maxVol){
    if(index == numProduct) return 0; // *기저사건 
    int& ret = cache[maxVol][index]; // index 이후의 물건들로 maxVol을 채울 때 최대 절박도
    if(ret != -1) return ret;

    

    // case 1. index아이템은 선택하지 않음
    ret = play(index+1, maxVol); 

    

    // case 2. index아이템을 선택함. 이 경우 무게제한은 maxVol-volume[index] 로 줄어듬
    if(volume[index]<=maxVol)
        ret = max(ret, play(index+1, maxVol-volume[index])+need[index]);
    return ret;
}
void reconstruct(int index, int maxVol){
    if(index == numProduct) return;
    if(play(index, maxVol) == play(index+1, maxVol))
        return reconstruct(index+1, maxVol);
    packed.push_back(product[index]);
    return reconstruct(index+1, maxVol-volume[index]);
}
int main(){
//    freopen("input.txt", "r", stdin);
    cin >> tc;
    while(tc--){
        packed.clear(); //packed 벡터 초기화
        memset(cache, -1, sizeof(cache)); // cache배열을 -1로 초기화
        cin >> numProduct >> maxVol;
        FOR(i, numProduct)
            cin >> product[i] >> volume[i] >> need[i];
        cout << play(0, maxVol) << " ";
        reconstruct(0, maxVol);
        cout << packed.size() << endl;
        FOR(i, packed.size())
            cout << packed[i] << endl;
    }
}