ある重さを量るのに使う錘の組み合わせは何通り?

問題: 1, 5, 10, 50, 100, 500グラムの6種類の錘があります。それぞれの錘はいくつでも使うことができます。ある重さを量るときに使う錘の組み合わせは何通りになりますか。それを求めるプログラムを書いてください。ここで量る重さはグラム単位の整数とし、最大で100キログラムとします。10グラムの重さを量る場合、10グラムの錘が1個、5グラムの錘が2個、5グラムの錘1個と1グラムの錘が5個、1グラムの錘が10個の組み合わせになり、全部で4通りとなります。

以下、解答例。

weights.cpp

// 指定した重さを量るのに使う錘の組み合わせの数を求めるプログラム. // 錘は 1g, 5g, 10g, 50g, 100g, 500g の6種類. // 重さ 700,000g 程度までなら桁あふれせずに計算できる. #include <iostream> #include <map> #include <algorithm> #include <cstdlib> using namespace std; const int weights[] = { 1, 5, 10, 50, 100, 500 }; // 錘(昇順). const int N = sizeof(weights) / sizeof(int); // 錘の種類. // 求めた錘の組み合わせの数のメモ. // 下位3ビットは使用する錘(solveのidx)を表す. // 残りのビットは重さ(solveのv)を表す. map<int, unsigned long long> memo; // 指定した重さに対する錘の組み合わせの数を求める. // v : 重さ // idx : 使用する錘 // N-1の場合はweights[0]からweights[N-1]までの錘を使用する(すべての錘). // 2の場合はweights[0]からweights[2]までの錘を使用する(1, 5, 10の錘). // 戻り値: 組み合わせの数 unsigned long long solve(int v, int idx=N-1) { // 既に計算済みであるならその結果を返す. if (memo.find(v<<3|idx) != memo.end()) return memo[v<<3|idx]; // 重さが0になったのならば新たな組み合わせが1つ見つかった. if (v == 0) return 1; unsigned long long cnt = 0; // 錘の種類だけループを回す. for (int i = idx; i >= 0; i--) // 重さが錘よりも軽い場合は次の錘. if (v >= weights[i]) // 求めた組み合わせの数をカウントに加える. cnt += solve(v - weights[i], i); // 求めた組み合わせの数をメモしておく. memo[v<<3|idx] = cnt; return cnt; } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " [weight]" << endl; exit(1); } cout << solve(atoi(argv[1])) << endl; return 0; }

この手のアルゴリズムの問題に慣れた人なら簡単だと思う。自分はこれと同類の問題を初めて聞いたときに即座に書けなかったので自戒を込めてここで書いてみた。

ところで、このコードで使っているメモ化だが、これをしないと実用的には使うことはできない。例えば、2,000グラムの組み合わせを求めた場合、メモ化していれば自分の環境では0.002秒で答えが出るが、メモ化していないと85秒も掛かる。因みにこの場合の組み合わせは4,443,355通り。