ナップサック問題

「重さが1,3,5,6,8 という5つの品物をいくつか選んで、最も10に近づけるにはどう組み合わせればいいか」
こういう問題のことをナップサック問題といいます。
今回は1,3,6と詰めれば、丁度10になりますが、どのように組みわせてもぴったりになることはない問題もあります
ナップサック問題

一次元のタイルパズルという感じで簡単そうに見えますが、完全に求めるには総当りしかない、結構厄介な問題です
品物の候補が100個ある場合、2^100通りの選び方があるのでとてもまともには計算できません

そこで、枝刈りポイントを探していきましょう
多くの場合は、100個の品物があっても、せいぜい入るのは10個前後でしょう
ですので、全てをチェックする必要がないことがわかります

入るパターンを効率よく探すために、以下のアルゴリズムで探索していきます
まず、メモを用意して、1個目の品物の重さを書きます
2個目は、2個目の品物の重さと、これまでメモに書いていた値と2個目の品物の重さを合計したものを書きます
ナップサックの限界を超えたものはメモには書きません
こうすることで効率よく重さの組み合わせを羅列することが出来ます

さらに、このメモには同じ重さの時は1つだけ残すようにします
こうすることで、際限なくメモが必要ということが避けられます

例として、15kg入るナップサックに1g単位の品物を入れることを考えます
ナップサックに入る重さは0～15000gの15001通りの値しかありません
ですから、15001個分のデータを保存できるメモリがあれば充分です

そんな感じでC++で組んだプログラムが以下になります

knapsack.cpp

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

std::vector<int> knapsack(const std::vector<int> &item, int limit){
	typedef std::map<int, int> MemorizeMap;
	MemorizeMap data;
	int index = 0;
	for (auto m : item){
		std::vector<int> add;
		for (auto d : data){
			int weight = d.first + m;
			if (weight <= limit) add.push_back(weight);
		}
		for (auto v : add) data.insert(MemorizeMap::value_type(v, index));
		data.insert(MemorizeMap::value_type(m, index));
		index++;
		if (!data.empty() && data.cbegin()->first == limit) break;
	}

	auto it = data.lower_bound(limit);

	std::vector<int> ret;
	for (;;){
		if (it == data.end()) break;
		ret.push_back(item[it->second]);
		int rest = it->first - item[it->second];
		if (rest == 0) break;
		it = data.find(rest);
	}

	return ret;
}

int main()
{
	std::vector<int> data;

	int total = 0;

	for (int i = 1; i <= 12; i++){
		int cube = i * i * i;
		data.push_back(cube);
		total += cube;
	}

	auto result = knapsack(data, total / 2);
	for (auto r : result){
		std::cout << r << std::endl;
	}

	return 0;
}

/*Output
1331
1000
343
216
125
27
*/

サンプルとして、1辺が1cm～12cmの1cm刻みの立方体が12個あって、
この重さ(1辺の3乗)が丁度二等分に近い分け方を探しだすパターンを出しています