POJ 1742 Coins

題意：
    有N種硬幣，每種硬幣價值A[i]元以及該種硬幣的數量為C[i]，問這些硬幣在最多總合為M元的限制下有幾種組合數?

想法：
    01背包，dp[i]=true表示i元可以被組合出來，最後看dp[1]~dp[M]有幾個true就是答案。這題時間限制嚴格，因此用POJ 1276那篇的方法還是會TLE，因此在底下code22行，我們知道如果j是從M~0表示一次放一個物品，每種要做C[i]次，現在22行j從0開始~M，是用無限背包的方式，先把物品當作無限個，類似greedy的方式，然後用個num陣列來計數，這樣每種物品都只要跑1次就可以了。

	#include <cstdio>
	#include <numeric>
	#include <algorithm>
	using namespace std;
	bool dp[100005];
	int num[100005];
	int main()
	{
	int N, M;
	int A[101], C[101];
	while (scanf("%d %d", &N, &M) && (N || M)) {
	for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
	for (int i = 0; i < N; ++i) scanf("%d", &C[i]);
	fill(dp, dp+M+1, false);
	dp[0] = true;
	for (int i = 0; i < N; ++i) {
	fill(num, num+M+1, 0);
	for (int j = 0; j+A[i] <= M; ++j)
	if (dp[j] == true && !dp[j+A[i]] && num[j] < C[i]) {
	dp[j+A[i]] = true;
	num[j+A[i]] = num[j] + 1;
	}
	}
	printf("%d\n", accumulate(dp+1, dp+M+1, 0)); // from dp[1] to dp[M]
	}
	}

view raw [POJ] 1742 Coins.cpp hosted with ❤ by GitHub