題意描述：
有幾種面額固定的硬幣，每種面額的硬幣都有無數張。給你一定的金額，問總共有多少種找零方案。
完全背包問題，動態方程為：f[j] += f[j - mny[i]];
myi[i]表示第i種硬幣的面值，f[j]表示數額為j的找零方案。
表示對完全背包的動態方程不甚理解，希望大神不惜指點。。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 350
#define LENM 20
int main()
{
int i, j;
int f[LEN];
int mny[LENM];
int n;
for(i = 1; i <= 17; i++)
mny[i] = i * i;
while(scanf("%d", &n), n)
{
memset(f, 0, sizeof(f));
f[0] = 1;
for(i = 1; i <= 17; i++)
for(j = mny[i]; j <= n; j++)
f[j] += f[j - mny[i]];
printf("%d\n", f[n]);
}
//system("pause");
}
posted on 2012-08-15 14:12
小鼠標 閱讀(287)
評論(0) 編輯 收藏 引用 所屬分類:
DP