Combinations of weights

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;
}

http://handasse.blogspot.com/2010/12/blog-post.html