読者です 読者をやめる 読者になる 読者になる

FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

SuperCon 2007 予選問題 問2

c/c++

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ってどうやって解くのん? 動的計画の応用だとメモリがボトルネックになって、あまり大きい額面のコインには対応できないんだよねー。