ナップザック問題の解き方

ナップザック問題とはどういう問題なのか、その解法を理解できるようにまとめたいと思います。

ナップザック問題の例題

価値がVi重さがWiであるようなN個の品物と、容量がWのナップザックがあります。
次の条件を満たすように、品物を選んでナップザックに入れます。

1.選んだ品物の価値の合計をできるだけ高くする
2.選んだ品物の重さの総和はWを超えないようにする

このような各品物を選択するかしないかの組み合わせの問題を0-1ナップザック問題といいます。

問題を考えると、N個の各品物を選択するか選択しないかの組み合わせを全て調べることになるので、
計算効率は0(N^2)ということになります。

0-1ナップザック問題は動的計画法により、0(NW)の効率で求めることができます。

0-1ナップザック問題の解法

まず、次のような役割の変数を用意します。

変数名例	役割
items[N + 1]	items[i].w,items[i].vにそれぞれ重さと価値を代入するための一元配列。 構造体などを使って定義します。
C[N + 1][W + 1]	i個目までの品物を考慮して、大きさWのナップザックに入れる場合の価値の合計の最大値をC[i][w]とする2次元配列

例を挙げると、C[1][3]には品物1番目におけるナップザック容量3における最大価値が入ることになり、
配列の末端であるC[N][W]には、全ての組み合わせにおける最大の価値が入ることになります。

考慮する品物の数iに対し、各iにおけるナップザックの重さwを増やしていき、
C[i][w]を更新していきます。
C[i][w]の値は

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

の大きいほうになります。
1はこの時点で、対象の品物iを選択する。
2はこの時点で、対象の品物iを選択しないという処理になります。

また、1の品物iを選択するケースでは、品物iの重さがwを超えない場合のみ選択されます。

では、例題を元に処理に流れを見ていきます。
入力は、例題の通り

4 5
4 2
5 2
2 1
8 3

つまり、
品物の最大数N = 4、ナップザックの最大容量W = 5となります。

0-1ナップザック問題の解法

要素が0のケース

要素が0のケースを考えます。
要素が0の場合は、C[0][Wまで]の要素をすべて0に初期化します。

要素が1のケース

要素が1の場合を考えます。

品物1の重さは2なので、大きさが1のナップザックには入れることができないので、C[1][1]は0となります。 大きさが2のナップザックには、品物1を入れることができます。
ここで、選択した場合は重さが0 + 4 = 4(幅がw = 2の斜めの矢印)、
選択しない場合は0(縦の矢印)となり、大きい方の4をc[1][2]に記録します。
大きさ3,4,5のナップザックについても、同様の処理をします。

要素が2のケース

大きさが1のナップザックに、品物2は入られないので、C[2][1]は0になります。
大きさが2,3,4,5のナップザックには、品物2を入れることができます。
C[2][4]ではC[1][2](品物2の重さが2なので、4 - 2で前の品物の価値最大値をチェックしたいので、C[1][2]となります。図の斜め矢印は品物の重さを示しています。) + 品物2の価値(つまり4 + 5)または、C[1][4](価値4)つまりこの品物を選ばないケースのいずれか大きい方を選びます。
C[2][5]も同様の考え方をします。

要素が3のケース

品物3の重さは1なので、大きさが1から5のナップザックに、品物3を入れることができます。
各々の大きさで、品物を選択する場合と選択しない場合の最適なケースを考えて、選択していきます。

要素が4のケース

大きさが1,2のナップザックに、品物4をいれることはできません。
斜めの矢印は重さを意味するので、容量を超えることは、斜めの矢印が配列オーバーすることを意味します。
大きさが3,4,5のナップザックには、品物4をいれることができるので、下図のように最適な選択をします

図でまとめる

C{N][W]が最大の価値になります。
斜めの矢印が選択した品物を表しており、
C{N][W]から斜めの矢印を逆にたどっていくと、選ぶべき品物がわかるようになっています。

ということで、品物の選択状況を別の2次元配列[i][w]に記憶しておけば、
最適解における品物の組み合わせを復元することができます。
2次元配列をG[i][w]とすると、品物iが選択するときをDIAGONAL、選択されなかった時をTOPとして、
変数定義をすることが一般的なようです(boolでももちろん可)。

例題をc++を使って解く

例題をc++を使って、解説を入れつつ解いてみたいと思います。

まず、必要な変数を定義します。

#define NMAX 105
#define WMAX 10005
// 選択する場合
#define DIAGONAL 1
// 選択しない場合
#define TOP 0

// 価値と重さを持った構造体を定義
struct Item {
    int value,weight;
};
// 品物の数(入力により決められる)
int N;
// ナップザックの容量(入力により決められる)
int W;
// 入力された品物の価値と重さを保存する配列
Item items[NMAX + 1];
// 各々に価値の最適解を入れておく配列
int C[NMAX + 1][WMAX + 1];
// 各々の品物を選択するか選択しないかを入れておく配列
int G[NMAX + 1][WMAX + 1];

続いて、図解で示した処理を行う関数を定義します。 コメントで処理内容の詳細を書きました

/**
    0-1ナップザック問題の解法を行う
    最大値を返す。
*/
int compute(){
    // 配列要素0を0で初期化(図参照)
    for(int w = 0;w <= W;++w){
        C[0][w] = 0;
        G[0][w] = DIAGONAL;
    }
    
    // C[1 to N)を0で初期化(図参照)
    for(int i = 1;i <= N;++i) C[i][0] = 0;
    
    // 図の要素1から要素の末尾までの処理を行う
    for(int i = 1;i <= N;++i){
        for(int w = 1;w <= W;++w){
            // 選択しなかったケースを代入しておく
            // 選択しなかったケースは図のように[i - 1]を重さを入れておく
            C[i][w] = C[i - 1][w];
            // Gは選択するかしないかを格納する配列、格納しないケースであるTOPを入れる
            G[i][w] = TOP;
            // 現時点でのナップザックの重さが対象の品物の重さ以上でないと、その品物を選択することができない
            if(items[i].weight > w) continue;
            // 左辺は対象の品物の価値と品物の重さを引いたC配列の最適解を加算したものを示しています。
            // 右辺はC[i - 1][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;
            }
        }
    }
    
    // C[N][W]が最大となる
    return C[N][W];
}

問題には関係ありませんが、選んだ品物を順番に表示するには、 以下のように処理を書きます。

/**
 選んだ品物を順番に表示する
*/
void printSelection(){
    vector selection;
    for(int i = N, w = W;i >= 1;--i){
        if(G[i][w] == DIAGONAL){
            selection.push_back(i);
            // 選んだ品物の重量を引く、斜め矢印の処理にあたる
            w -= items[i].weight;
        }
    }
    
    reverse(selection.begin(),selection.end());
    
    for (int i = 0;i < selection.size();++i) {
        printf("%d ",selection.at(i));
    }
}

プログラムの全体は以下のようになります。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define NMAX 105
#define WMAX 10005
// 選択する場合
#define DIAGONAL 1
// 選択しない場合
#define TOP 0

// 価値と重さを持った構造体を定義
struct Item {
    int value,weight;
};
// 品物の数(入力により決められる)
int N;
// ナップザックの容量(入力により決められる)
int W;
// 入力された品物の価値と重さを保存する配列
Item items[NMAX + 1];
// 各々に価値の最適解を入れておく配列
int C[NMAX + 1][WMAX + 1];
// 各々の品物を選択するか選択しないかを入れておく配列
int G[NMAX + 1][WMAX + 1];

/**
    0-1ナップザック問題の解法を行う
    最大値を返す。
*/
int compute(){
    // 配列要素0を0で初期化(図参照)
    for(int w = 0;w <= W;++w){
        C[0][w] = 0;
        G[0][w] = DIAGONAL;
    }
    
    // C[1 to N)を0で初期化(図参照)
    for(int i = 1;i <= N;++i) C[i][0] = 0;
    
    // 図の要素1から要素の末尾までの処理を行う
    for(int i = 1;i <= N;++i){
        for(int w = 1;w <= W;++w){
            // 選択しなかったケースを代入しておく
            // 選択しなかったケースは図のように[i - 1]を重さを入れておく
            C[i][w] = C[i - 1][w];
            // Gは選択するかしないかを格納する配列、格納しないケースであるTOPを入れる
            G[i][w] = TOP;
            // 現時点でのナップザックの重さが対象の品物の重さ以上でないと、その品物を選択することができない
            if(items[i].weight > w) continue;
            // 左辺は対象の品物の価値と品物の重さを引いたC配列の最適解を加算したものを示しています。
            // 右辺はC[i - 1][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;
            }
        }
    }
    
    // C[N][W]が最大となる
    return C[N][W];
}

int main(){
    int maxValue;
    // 入力処理
    cin >> N >> W;
    for(int i = 1;i <= N;++i){
        cin >> items[i].value >> items[i].weight;
    }
    maxValue = compute();
    
    cout << maxValue << endl;
    return 0;
}

参考
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造