여행 짐 싸기

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

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 가져가고 싶은 물건의 수 N (1≤N≤100)과 캐리어의 용량 W (1≤W≤1000)가 주어집니다. 그 이후 N줄에 순서대로 각 물건의 정보가 주어집니다. 한 물건에 대한 정보는 물건의 이름, 부피, 절박도 순서대로 주어지며, 이름은 공백 없는 알파벳 대소문자 1글자 이상 20글자 이하의 문자열, 부피와 절박도는 1000 이하의 자연수입니다.

출력

각 테스트 케이스별 출력의 첫 줄에는 가져갈 수 있는 물건들의 최대 절박도 합과 가져갈 물건들의 개수를 출력합니다. 이후 한 줄에 하나씩 각 물건들의 이름을 출력합니다. 만약 절박도를 최대화하는 물건들의 조합이 여럿일 경우 아무 것이나 출력해도 좋습니다.

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

#include <vector>

using namespace std;

int N, W;

string name[100];

int volume[100] , need[100];

int cache[1001][101];

int find(int capacity, int item)

{

if (item == N) return 0; // 더 이상 담을 물건이 없을때

int& ret = cache[capacity][item];

if (ret != -1)

return ret;

ret = find(capacity, item + 1); // 이 물건을 담지 않을 경우

if (capacity >= volume[item])

ret = max(ret, find(capacity - volume[item], item + 1) + need[item]); // 이 물건을 담는 경우

return ret;

}

void reconstruct(int capacity, int item, vector<string>& list) // 선택한 물건들의 목록을 list에 저장

{

if (item == N) return; //모든 물건을 고려했을때

if (find(capacity, item) == find(capacity, item + 1)) // item과 item+1의 find가 같다면 name[item]은 고르지 않았을 것

reconstruct(capacity, item+1, list);

else {

list.push_back(name[item]);

reconstruct(capacity-volume[item], item + 1, list);

}

}

int main()

{

int C;

cin >> C;

while (C--)

{

memset(cache, -1, sizeof(cache));

cin >> N >> W;

for (int i = 0; i < N; ++i) {

cin >> name[i] >> volume[i] >> need[i];

}

int maxneed = find(W, 0);

vector<string> list;

reconstruct(W, 0, list);

cout << maxneed << " " << list.size() << endl;

for (int i = 0; i < list.size(); ++i)

cout << list[i] << endl;

}

return 0;

}