ナップサック問題の最適解復元
概要¶
ナップサック問題の DP で最適値（価値の最大値）だけでなく、実際にどの品物を選んだかを復元する方法。
動的計画法の最適解復元の方法 2（伝播元メモ方式）を適用する。
ナップサック問題¶
\(n\) 個の品物があり、\(i\) 番目の品物の重さを \(weight[i]\)、価値を \(value[i]\) とする。 重さの総和が \(W\) を超えないように選んだときの、価値の総和の最大値を求め、さらに選んだ品物を列挙する。
制約 - \(1 \leq n \leq 100\) - \(1 \leq weight[i], value[i] \leq 1000\) - \(1 \leq W \leq 10000\)
数値例 \(n=6\), \((weight, value) = (2,3),(1,2),(3,6),(2,1),(1,3),(5,85)\), \(W=8\) 答え: \(91\)（品物 \((3,6)\) と \((5,85)\) を選ぶ）
DP テーブルの定義¶
DP 更新式¶
品物 \(i\)（0-indexed）について:
-
品物 \(i\) を選ぶ場合 (\(w \geq weight[i]\)): \(dp[i+1][w] = \max(dp[i+1][w],\ dp[i][w - weight[i]] + value[i])\)
-
品物 \(i\) を選ばない場合: \(dp[i+1][w] = \max(dp[i+1][w],\ dp[i][w])\)
出典: 意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法
復元用テーブル¶
prev_w[i+1][w] = dp[i+1][w] が dp[i][prev_w[i+1][w]] から更新されたことを示す。
- 品物 \(i\) を選んだ場合:
prev_w[i+1][w] = w - weight[i] - 品物 \(i\) を選ばなかった場合:
prev_w[i+1][w] = w
完全な実装 (C++)¶
#include <iostream>
using namespace std;
int n, W;
int weight[110], value[110];
int dp[110][10010] = {0};
int prev_w[110][10010];
int main() {
cin >> n >> W;
for (int i = 0; i < n; ++i) cin >> value[i] >> weight[i];
// DP ループ
for (int i = 0; i < n; ++i) {
for (int w = 0; w <= W; ++w) {
// 品物 i を選ぶ場合
if (w >= weight[i]) {
if (dp[i+1][w] < dp[i][w-weight[i]] + value[i]) {
dp[i+1][w] = dp[i][w-weight[i]] + value[i];
prev_w[i+1][w] = w - weight[i]; // 伝播元をメモ
}
}
// 品物 i を選ばない場合
if (dp[i+1][w] < dp[i][w]) {
dp[i+1][w] = dp[i][w];
prev_w[i+1][w] = w; // 重さ変化なし
}
}
}
cout << dp[n][W] << endl;
// 復元
cout << "Selected items are..." << endl;
int cur_w = W;
for (int i = n-1; i >= 0; --i) {
// 重さが変化していれば品物 i を選んでいた
if (prev_w[i+1][cur_w] == cur_w - weight[i]) {
cout << i << " th item (weight = " << weight[i]
<< ", value = " << value[i] << ")" << endl;
}
cur_w = prev_w[i+1][cur_w];
}
}
出力例¶
91
Selected items are...
5 th item (weight = 5, value = 85)
4 th item (weight = 1, value = 3)
0 th item (weight = 2, value = 3)
復元ロジックの解説¶
prev_w[i+1][cur_w] == cur_w - weight[i] が成り立てば、品物 \(i\) を選んでいたことがわかる。
等しくなければ prev_w[i+1][cur_w] == cur_w であり、品物 \(i\) は選ばなかった。