ナップザック問題 Knapsack Problem

大きさ w と価値 v を持った品物が N 個あり、これらを大きさ W のナップザックに入れたいとします。このとき、大きさの合計が W を超えず、価値の合計が最大になるような品物の組み合わせを求めたい。これがナップザック問題です。各品物を「選択する」か「選択しない」かの組み合わせなので、厳密には0-1ナップザック問題ともいいます。(各品物が複数個ある場合は、0123ナップザック問題と呼ばれます)

この問題を力任せで解こうとすれば、N 個の品物を「選択する」か「選択しないか」の全組み合わせを全て調べることになるので、計算効率は O(2^N) となります。N が数十個でも、実用的な時間では計算できません。

品物の大きさ w、ナップザックの大きさ W がともに整数であれば、ナップザック問題は動的計画法により O (NW) の効率で厳密解を求めることができます。

C[i][w] が、大きさ w のナップザックに品物を 0 から i 個目まで考慮した時の価値の合計の最大値、となるような (N+1) × (W+1) の２次元配列 C を準備します。

C[i][w] の値は、

(1) C[i - 1][w - 品物 i の重さ] + 品物 i の価値、　または
(2) C[i - 1][w]

の大きい方となります。ここで、(1)はこの時点で品物 i を選択する、（２）はこの時点で品物 i を選択しない、という処理に対応します。ただし、（１）の場合は、品物 i の重さが w を超えない場合に限ります。

例を見てみましょう。

ナップザックの大きさ w が 0、または品物の数 i が 0 個の場合は、価値の合計が 0 なので、w = 0 と i = 0 の部分を 0 に初期化します。 大きさ w が 1 のナップザックに、品物 1 を入れてみる。 しかし、品物 1 の大きさは 2 で、容量を超えるので、無条件で品物 1 は選択しない（できない）。 大きさ w が 2 のナップザックに、品物 1 を入れてみる。 ここで、品物 1 の大きさは 2 なので選択可能。 (1) 選択した場合は 0 + 4 = 4 （斜めの矢印）、 (2) 選択しない場合は 0　（縦の矢印）, なので、C[i][w] = C[1][2] に 4 を記録する。 大きさ w が 3, 4, 5 についても同様。 大きさ w が 1 のナップザックに、品物 2 を入れてみる。 しかし、品物 2 の大きさは 2 で、容量を超えるので、無条件で選択しない。 大きさ w が 2 ～ 5 のナップザックに、品物 2 を入れてみる。 C[2][4] に注目してみましょう。ここでは (1) C[1][2] + 品物 2 の価値　（= 4 + 5）または (2) C[1][4]　（= 4）` のいづれか大きいほうを選びます。 大きさ w が 1 ～ 5 のナップザックに、品物 3 を入れてみる。 同様に C[i][w] を計算する。 品物 3 の重さが 1 なので、斜めの矢印の幅が 1 になる。 大きさ w が 1, 2 のナップザックに、品物 4 を入れてみる。 しかし、品物 4 の大きさは 3 で、容量を超えるので、選択できない。 容量を超えるとは、斜めの矢印が配列からはみ出してしまうことに相当する。。 大きさ w が 3, 4, 5 のナップザックに、品物 4 を入れてみる。 今度は、大きさが 3 なので、矢印の幅は 3 。 C[N][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;
    }
    
}