[UVa]147:Dollars

這題是DP的找零錢問題。

有幾種組合的算法，
由於可能會有重覆算到的關係，
所以要先加入最小的零錢(此題是5c)進去，
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
接著再把次小的零錢(此題是10c)放進去，
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
這樣以此類推到最大的零錢，
這樣我在算最後一個零錢是10c的組合的時候，
我只會找出5c跟10c的組合，
不會找出配上20c啦...50c啦...或是1元之類的組合。
等到我在算最後一個零錢是20c的組合的時候，
我只會找出5c跟10c跟20c的組合，
不會找出配上50c啦...或是1元之類的組合。
(如果看不懂以上內容，可以翻閱關於DP找零錢問題的教學文章。)

再來應該要建dp表，我們不可能用小數當索引值，
所以我們可以把該值乘上100在對應dp的那格為其答案，
但是浮點數乘法再配上轉成整數是避不開誤差的Orz...
因此請善用兩個整數來存值XD

[C](0.020)

	#include<stdio.h>
	int main()
	{
	long long dp[30005] = {1};
	long long possible[15] = { 5, 10, 20, 50,
	100, 200, 500,
	1000, 2000, 5000,
	10000};
	int i, j;
	for( i = 0 ; i < 11 ; i++ )
	for( j = possible[i] ; j <= 30000 ; j++ )
	dp[j] += dp[j-possible[i]];
	int money1, money2;
	while( scanf( "%d.%d", &money1, &money2 ) != EOF && !( money1 == 0 && money2 == 0 ) )
	printf( "%3d.%02d%17lld\n", money1, money2, dp[money1*100+money2] );
	return 0;
	}

view raw UVa147.c hosted with ❤ by GitHub