競技プログラミング風 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となる。
[java] #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;
}
[/java]

ヒント

・全アイテム（i = 0…N-1）について、アイテムを入れた場合と入れない場合を調べればいいぞ。
・knapsac() 関数の下請けとして、アイテムの ix 要素以降を調べる関数を用意するといいぞ。
・knapsac() 下請け関数は同じ引数で何度もコールされるので、結果を保存して再利用（メモ化）するといいぞ。

解答例

[java] #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
[/java]

解説

下請け関数として、最大価値を返す 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 での計算が何度も行われないので、処理時間が大幅に高速化される。