[PACKING] 여행짐싸기

[PACKING] 여행짐싸기

• 분류: 동적계획법
• 난이도: 중
• 입력: 테스트 케이스 C, 물건의 수 N, 캐리어의 용량 W, N개의 물건의 이름, 부피, 절박도 
• 출력: 가져갈 수 있는 물건들의 최대 절박도의 합과 가져갈 물건들의 갯수. 단, 조합이 여럿일 경우 아무거나 출력해도 됨.
• 소스

#include <iostream> #include <fstream> #include <algorithm> #include <vector> using namespace std; int n, capacity; int volume[100], need[100]; int cache[1001][100]; string name[100]; 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 >= volume[item]) ret = max(ret, pack(capacity - volume[item], item + 1) + need[item]); return ret; } void reconstruct(int capacity, int item, vector<string>& picked){ if (item == n) return; if (pack(capacity, item) == pack(capacity, item + 1)){ reconstruct(capacity, item + 1, picked); } else{ picked.push_back(name[item]); reconstruct(capacity - volume[item], item + 1, picked); } } int main(){ int C; cin >> C; for (int i = 0; i < C; i++){ cin >> n >> capacity; vector<string> picked; for (int j = 0; j < n; j++){ in >> name[j] >> volume[j] >> need[j]; for (int m = 0; m < 1001; m++) cache[m][j] = -1; } <> reconstruct(capacity, 0, picked); cout << pack(capacity, 0) << " " << picked.size() << endl; for (int j = 0; j < picked.size(); j++) cout << picked[j] << endl; } return 0; }

• 소스 설명:
1. pack(int capacity, int item) : 최대절박도를 계산하는 함수로, 동적계획법을 사용하였다. 해당 물건을 가져가나 마느냐를 체크하므로 for문이나 while문은 사용하지 않는다. 
2. reconstruct(int capacity, int item, vector<string>& picked) : 계산된 절박도를 이용하여, 가져갈 목록을 역추적한다.
• 참고 사이트:https://algospot.com/judge/problem/read/PACKING
• 참고 소스 코드: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1