SuperCon 2007 予選問題 問2

• SuperCon 2007 予選問題（PDF）

「Algorithms with Python / 欲張り法, 動的計画法」を参考にしつつ、動的計画法で普通に実装してみた。「普通に」実装するまでにどんだけ時間かかってるんだ、っていう。確認した限りでは正しい答えを導いてくれるはず。計算に掛かる時間は、金額に最大値の1000万円を放り込んだとしても1秒かからないくらい。

厳密な答えが出るのはいいんだけど、動的計画法による解法はオーソドックスすぎる嫌いがあるし、メモリも大量に食うから最善とは言い切れない。コンテストで意外性を狙うなら、局所探索とかのヒューステリックな方法を採用したほうがポイントは高いかも？

// DPでコインの組み合わせを探索
void select_coin(int amount, int *coin, int k)
{
	int *num, *kind, result[10] = { 0 };
	int i, j, space, total = 0;
	
	// メモリ確保
	num  = calloc(amount+1, sizeof(int));
	kind = calloc(amount+1, sizeof(int));
	
	// DPの主要部分
	for (i = 0; i < k; i++) {
		for (j = coin[i]; j <= amount; j++) {
			// コインを1枚採用したときの余り
			space = j - coin[i];
			// テーブルを更新
			if (num[j] == 0 || 1 + num[space] < num[j]) {
				kind[j] = i;
				num[j] = 1 + num[space];
			}
		}
	}
	
	// コインの組み合わせを算出
	while (amount) {
		result[ kind[amount] ]++;
		total++;
		amount -= coin[ kind[amount] ];
	}
	
	// 組み合わせを出力
	for (i = k - 1; i >= 0; i--) {
		printf("%d %d\n", coin[i], result[i]);
	}
	printf("%d\n", total);
}

つーか問3ってどうやって解くのん？ 動的計画の応用だとメモリがボトルネックになって、あまり大きい額面のコインには対応できないんだよねー。