AOJ - PACKING

AOJ - PACKING

냅색 문제인데, 정답을 역추적 해야한다. 역추적하는 방법엔 여러가지가 있겠지만, 일단 슬라이딩 윈도우로 1차원 배열만 선언해놓고 구할 순 없다는 것이다.

무조건 2차원으로 $\mathit{choice}[i][w]$ 를 두고 $i$ 번째 아이템까지 쓸 수 있고 무게 $w$를 쓸 수 있을 때 마지막으로 고른 것 이라는 배열을 관리한다.

$i=n-1 ~\&~ w=W$ 일 때가 항상 최대값이고, 이때부터 역추적을 시작해준다.

$\mathit{choice}[n-1][W]=k$ 라면 일단 마지막으로 고른 아이템은 $k$이고 다음은$\mathit{choice}[k-1][W-W_k]$ 로 점프하면 된다.

이렇게 반복문으로 구하지않고 재귀함수로 구할 수 있는 방법이 책에 소개된다.

코드 9.3 여행 짐 싸기 문제의 답 역추적하는 재귀 호출 알고리즘
//pack(capacity,item)이선택한물건들의목록을picked에저장한다. 
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);
   }
}

struct item {  
   string name;  
   int w, v;  
};  
  
void solve() {  
   int n, w;  
   cin >> n >> w;  
  
   vector<item> arr;  
   for (int i = 0; i < n; i++) {  
      item k;  
      cin >> k.name >> k.w >> k.v;  
      arr.pb(k);  
   }  
  
   vvi dp(n, vi(w + 1));  
   vvi choice(n, vi(w + 1, -1));  
   for (int j = arr[0].w; j <= w; j++) {  
      dp[0][j] = arr[0].v;  
      choice[0][j] = 0;  
   }  
   for (int i = 1; i < n; i++) {  
      for (int j = 0; j <= w; j++) {  
         dp[i][j] = dp[i - 1][j];  
         choice[i][j] = choice[i - 1][j];  
         if (j >= arr[i].w && dp[i - 1][j - arr[i].w] + arr[i].v > dp[i][j]) {  
            dp[i][j] = dp[i - 1][j - arr[i].w] + arr[i].v;  
            choice[i][j] = i;  
         }  
      }  
   }  
   cout << dp[n - 1][w] << ' ';  
   vs ans;  
  
   int a = n - 1;  
   int b = w;  
   while (a >= 0 && b > 0 && choice[a][b] != -1) {  
      int pa = a;  
      ans.pb(arr[choice[a][b]].name);  
      a = choice[pa][b] - 1;  
      b -= arr[choice[pa][b]].w;  
   }  
   reverse(all(ans));  
   cout << sz(ans) << endl;  
   for (string s: ans) cout << s << endl;  
}