uva147 - Dollars（完全背包）

uva147 - Dollars（完全背包）

題目：uva147 - Dollars（完全背包）

題目大意：給出11種硬幣，然後給出一個數字，問可以有多少方式由上面的給的硬幣湊出。這裡要注意精度誤差，題目可能會給出20.005這樣的數據，雖然我覺得這是不合法的數據，但是但是會給，並且還需要你向上取整。

解題思路：完全背包。

代碼：

#include 
#include 

const int N = 11;
const int maxn = 30005;
const int c[N] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

typedef long long ll;

ll f[maxn];

void  init () {

	memset (f, 0, sizeof (f));
	f[0] = 1;
	for (int i = 0; i < N; i++)
		for (int j = c[i]; j <= maxn - 5; j++)
			f[j] += f[j - c[i]];
}

int main () {
	
	init();
	float num;
	int n;
	while (1) {
		scanf ("%f", &num);
		n = (num + 0.005) * 100;
		if (!n)
			break;
		printf ("%6.2f%17lld\n", num, f[n]);
	}
	return 0;
}