ナップザック問題 Knapsack Problem
2007.02.07 13:47 動的計画法

大きさ w と価値 v を持った品物が N 個あり、これらを大きさ W のナップザックに入れたいとします。このとき、大きさの合計が W を超えず、価値の合計が最大になるような品物の組み合わせを求めたい。これがナップザック問題です。各品物を「選択する」か「選択しない」かの組み合わせなので、厳密には0-1ナップザック問題ともいいます。(各品物が複数個ある場合は、0123ナップザック問題と呼ばれます)
この問題を力任せで解こうとすれば、N 個の品物を「選択する」か「選択しないか」の全組み合わせを全て調べることになるので、計算効率は O(2N) となります。N が数十個でも、実用的な時間では計算できません。
品物の大きさ w、ナップザックの大きさ W がともに整数であれば、ナップザック問題は動的計画法により O (NW) の効率で厳密解を求めることができます。
C[i][w] が、大きさ w のナップザックに品物を 0 から i 個目まで考慮した時の価値の合計の最大値、となるような (N+1) × (W+1) の2次元配列 C を準備します。
C[i][w] の値は、
(1) C[i - 1][w - 品物 i の重さ] + 品物 i の価値、 または
(2) C[i - 1][w]
の大きい方となります。ここで、(1)はこの時点で品物 i を選択する、(2)はこの時点で品物 i を選択しない、という処理に対応します。ただし、(1)の場合は、品物 i の重さが w を超えない場合に限ります。
例を見てみましょう。
#include<iostream> #include<vector> #define MAX 100 #define DIAGONAL 1 #define LEFT 0 using namespace std; /** * Target 624, 10130, * */ struct Item{ int value, weight; }; int n; Item items[MAX]; int C[MAX+1][MAX+1], G[MAX+1][MAX+1]; int weight; void compute( int &maxValue, vector<int> &path ){ for ( int w = 0; w <= weight; w++ ) { C[0][w] = 0; G[0][w] = DIAGONAL; } for ( int i = 1; i <= n; i++ ) C[i][0] = 0; for ( int i = 1; i <= n; i++ ){ for ( int w = 1; w <= weight; w++ ){ if ( items[i].weight <= w ){ if ( items[i].value + C[i-1][w - items[i].weight] > C[i-1][w] ){ C[i][w] = items[i].value + C[i-1][w - items[i].weight]; G[i][w] = DIAGONAL; }else{ C[i][w] = C[i-1][w]; G[i][w] = LEFT; } }else { C[i][w] = C[i-1][w]; G[i][w] = LEFT; } } } maxValue = C[n][weight]; path.clear(); int w = weight; for ( int i = n; i >=1; i-- ){ if ( G[i][w] == DIAGONAL ){ path.push_back( i ); w -= items[i].weight; } } reverse( path.begin(), path.end() ); } void input(){ cin >> n >> weight; for ( int i = 1; i <= n; i++ ){ cin >> items[i].value >> items[i].weight; } } main(){ int maxValue; vector<int> path; input(); compute( maxValue, path); cout << "max " << maxValue << endl; for ( int i = 0; i < path.size(); i++ ) cout << path[i] << endl; for ( int i = 1; i <= n; i++ ){ for ( int j = 1; j <= weight; j++ ) { printf("%5d", C[i][j]); } cout << endl; } }
スポンサーサイト
| コメント(2) | トラックバック(0) | ↑ページトップ |