uva 674 Coin Change（類似完全背包）

有點類似完全背包，不過最後的容量必須被充滿。

dp[i][j]表示在前i個物品中選擇容量不超過j的最大價值。

完全背包轉移方程：dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i]]+w[i])

這道題目設數組dp[i][j]表示用前j個硬幣組成i的種類個數，轉移方程：dp[i][j] = dp[i-1][j]+dp[i][j-

a[i]]因為這裡求得是解的個數，所以要用加法，完全背包是求某一種情況所以去最大的。（明天實現一下一維數

組）

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
int a[6] = {0,1,5,10,25,50}; 
int dp[7500][7];
int main()
{
	int i,j,n;
	for(i=1; i<=5; i++)
		dp[0][i] = 1;
	for(i=1; i<=7490; i++)
		dp[i][0] = 0;
	for(i=1; i<=7489; i++)
	{
		for(j=1; j<=5; j++)
		{
			if(i >= a[j])
				dp[i][j] += dp[i][j-1]+dp[i-a[j]][j];
			else
				dp[i][j] = dp[i][j-1];
		}
	}
	while(cin >> n)
	{
		cout << dp[n][5] << endl;
	}
	return 0;
}