競技プログラミング風 C++問題集【第16回】

競技プログラミング風 C++問題集【第16回】

0/1ナップサック問題（難易度：★★★★☆）

問題

質量 wi、価値 vi のアイテムがN個（i = 0, … N-1）あり、それを合計質量 WT まで入れることができるナップサック（knapsack、リュックサック・バックパックの古い呼び名のひとつ）がある時、どのアイテムを入れると、価値の合計が最大になるか？という問題を「0/1 ナップサック問題」と呼ぶ。

質量合計上限、const vector<int>& 型の各アイテムの質量配列・価値配列を引数で受け取り、価値合計の最大値を返す関数 int maxValue(int WT, const vector<int>& wt, const vector<int>& val) を実装しなさい。

ただし、wt と val のサイズは同一とし、それぞれのサイズは100以下とする。

例えば、質量・価値が {10, 60}, {20, 100}, {30, 120} の３つのアイテムがあり、質量合計上限が40の場合、合計価値の最大値は、1番目・3番目をナップサックに入れた場合なので、180となる。

#include <iostream>       //  標準入出力ライブラリ
#include <vector>
#include <unordered_map>
#include <random>
#include <chrono>
using namespace std;    //  std 名前空間使用
std::mt19937 g_mt(0);            // メルセンヌ・ツイスタの32ビット版、引数は初期シード
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
int maxValue(int WT, const vector<int>& wt, const vector<int>& val) {
    return 0;
}
int main() {
    DO_TEST(maxValue(30, { 10, 20, 30 }, { 60, 100, 120 }) == 160);
    DO_TEST(maxValue(40, { 20, 30, 10 }, { 60, 100, 120 }) == 220);
    DO_TEST(maxValue(50, { 10, 30, 20 }, { 100, 60, 110 }) == 210);
    DO_TEST(maxValue(50, { 30, 20, 40, 10 }, { 60, 100, 120, 150 }) == 270);
    DO_TEST(maxValue(60, { 10, 20, 30, 40 }, { 60, 100, 120, 150 }) == 280);
    DO_TEST(maxValue(70, { 10, 20, 30, 40 }, { 60, 100, 120, 150 }) == 310);
    DO_TEST(maxValue(80, { 10, 20, 30, 40 }, { 60, 100, 120, 150 }) == 330);
    DO_TEST(maxValue(80, { 10, 20, 30, 40, 50, 60 }, { 60, 100, 120, 150, 160, 170 }) == 330);
    DO_TEST(maxValue(100, { 10, 20, 30, 40, 50, 60 }, { 60, 100, 120, 150, 160, 170 }) == 430);
    //
    if (1) {
        const int N = 100;  //  アイテム数
        const int SUM = (N+1)*N/2 * 10;
        vector<int> wt(N), val(N);
        int w = 0;
        for (auto& x : wt) x = (w += 10);
        for (auto& x : val) x = (g_mt() % 100 + 1) * 10;
        auto start = std::chrono::system_clock::now();      // 計測スタート時刻を保存
        maxValue(SUM/2, wt, val);
        auto end = std::chrono::system_clock::now();       // 計測終了時刻を保存
        auto dur = end - start;        // 要した時間を計算
        auto msec = std::chrono::duration_cast<std::chrono::milliseconds>(dur).count();
        cout << msec << "milliseconds.\n";
        DO_TEST( msec < 1000 );     //  1秒未満で解けたか？
    }
    //
    cout << "\nGood Job!\n";
    return 0;
}

ヒント

解答例

#if 0
//  バックトラッキング版、処理時間：O(2^wt.size())
//	質量上限：WT、質量・価値配列の ix 以降有効
int knapsack(int WT, const vector<int>& wt, const vector<int>& val, int ix) {
    if( WT <= 0 || ix >= wt.size() )
        return 0;
    if( wt[ix] > WT )   //  wt[ix] が質量上限より大きければ、ix 番目はナップサックに入れれない
        return knapsack(WT, wt, val, ix+1);     //  ix+1 以降の最大値を求める
    else
        return std::max(val[ix] + knapsack(WT - wt[ix], wt, val, ix+1),      //  ix番目を入れた場合
                        knapsack(WT, wt, val, ix+1));                       //  ix番目を入れない場合
}
int maxValue(int WT, const vector<int>& wt, const vector<int>& val) {
    if (wt.size() != val.size()) return -1;     //  Error
    return knapsack(WT, wt, val, 0);
}
#else
//  メモ化を用いる版、処理時間：O(wt.size() * WT)
//	質量上限：WT、質量・価値配列の ix 以降有効
unordered_map<__int64, int> g_map;
int knapsackONW(int WT, const vector<int>& wt, const vector<int>& val, int ix) {
    if( WT <= 0 || ix >= wt.size() )
        return 0;
    __int64 key = ((__int64)WT << 32) | ix;     //  上位32ビット：WT、下位32ビット：インデックス
    if( g_map.find(key) != g_map.end() ) return g_map[key];     //  既に計算済みの場合
    int v;
    if (wt[ix] > WT)   //  wt[ix] が質量上限より大きければ、ix 番目はナップサックに入れれない
        v = knapsackONW(WT, wt, val, ix + 1);     //  ix+1 以降の最大値を求める
    else
        v = std::max(val[ix] + knapsackONW(WT - wt[ix], wt, val, ix + 1),      //  ix番目を入れた場合
            knapsackONW(WT, wt, val, ix + 1));                       //  ix番目を入れない場合
    return g_map[key] = v;      //  計算結果を保存し、それを返す
}
int maxValue(int WT, const vector<int>& wt, const vector<int>& val) {
    if (wt.size() != val.size()) return -1;     //  Error
    g_map.clear();
    return knapsackONW(WT, wt, val, 0);
}
#endif

解説

下請け関数として、最大価値を返す int knapsack(int WT, const vector<int>& wt, const vector<int>& val, int ix) を定義する。WT は合計質量上限、wt, val は各アイテムの質量・価値配列。そして ix は配列のどの要素から有効かを示すインデックスだ（wt[ix] ～wt.back() までが有効）。
この関数は再帰的にコールされるので、最初に終了判定を行う。具体的には、WT が0以下、またはixが配列末尾要素を超えている場合は、ナップサックに何も入れることはできないので 0 を返す。
次に wt[ix] と WT を比べ、前者が後者を超えている場合は、ナップサックに ix 番目のアイテムを入れることはできないので、 knapsack(WT, wt, val, ix+1); と ix をひとつ進めて自分自身を再帰コールする。
wt[ix] が WT 以下の場合は、ix 番目をナップサックに入れる場合と入れない場合があるので、それぞれの場合について自分自身をコールして最大値を求め、それらの大きい方を返す。
ここまでが、解答例の前半の #if でコメントアウトされた部分だ。

上記は単純な再帰関数版で、それでも答えは求まるのだが、処理時間が O(2^N) となり、アイテム数Nが大きくなると膨大な時間を要してしまうことになる。
処理時間を短縮する有効な方法として、一度計算した結果をメモしておき、同じ引数で関数がコールされた場合は、再帰的に値を計算せずメモしておいた値を返す、というものがある。これを「メモ化」と呼ぶ。
もちろんこの方法が効果的なのは、同じ引数の値で関数が何度も呼ばれる場合だ。0/1ナップサック問題ではixをプラス１して下請け関数を呼び、それがまた下請け関数を呼ぶ、となっているので、同じ引数の値で関数が何度も呼ばれることになる。よって、メモ化を行うと処理時間が大幅に短縮されるということだ。
メモ化の具体的方法は以下のように行っている。
unordered_map<__int64, int> g_map; を定義しておき、WT と ix の組を64ビットにした数値をキーにし、合計最大値を値とする unordered_map を用意しておく。んで、knapsackONW() の最初の方で、質量上限・ix の組が g_map に登録済みがどうかをチェックし、登録済みであれば、その値を返す。そうでなければ再帰的に計算を行い、結果を g_map に保存しておく。
このようにしておくと、同じ WT, ix での計算が何度も行われないので、処理時間が大幅に高速化される。