v奶牛Bassie去DQ打工，遇到一个客人给了一张好大面值的钞票，于是Bassie不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有n种硬币，对这些不同种的硬币进行编号，编号为i的硬币面值为c[i] 。因为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为total)(1<=total<=1000,1<=n<=1000,1<=c[i]<=300) v求一共有多少种解决方案？ v【输入】 v 第一行为硬币总值total和硬币种类数n。 v 以下n行为数值c[i]，i=1,2,3...n v【输出】 v 一行，解决方案数
Sol:本题求方案数，递推，完全背包问题。设ans[i][j]表示用前i种硬币组成j元钱的方案数。对于第i种硬币，有用和不用两种选择，如果不用，ans[i][j]等于ans[i-1][j]（即等于前i-1种硬币组成j元钱的方案数），如果用，ans[i][j]等于ans[i][j-c[i]](即等于前i种硬币组成j-c[i]元钱的方案数。注意这里是ans[i][j-c[i]]，而不是ans[i-1][j-c[i]]，因为是无限背包）。从而得到递推式：ans[i][j]=ans[i-1][j]+ans[i][j-c[i]]。边界：ans[i][0]=1,0<=i<=n,即前i种硬币构成0元钱的方案数为1.
1 #include<bits/stdc++.h> 2 using namespace std; 3 int c[1005]; 4 long long ans[1005][1005]; 5 int main() 6 { 7 int n,total; 8 cin>>n>>total; 9 ans[0][0]=1; 10 for (int i=1;i<=n;i++) 11 { 12 cin>>c[i]; 13 ans[i][0]=1; 14 } 15 for (int i=1;i<=n;i++) 16 for (int j=1;j<=total;j++) 17 { 18 ans[i][j]=ans[i-1][j]+ans[i][j-c[i]]; 19 //注意加号后面的ans[i][j-c[i]],因为是无限背包，允许重复用多次 20 } 21 cout<<ans[n][total]<<endl; 22 return 0; 23 }
一维的写法：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int c[1005]; 4 long long ans[1005]; 5 int main() 6 { 7 int n,total; 8 cin>>n>>total; 9 ans[0]=1; 10 for (int i=1;i<=n;i++) 11 cin>>c[i]; 12 for (int i=1;i<=n;i++) 13 for (int j=0;j<=total;j++) 14 if (j-c[i]>=0) 15 ans[j]+=ans[j-c[i]]; 16 cout<<ans[total]<<endl; 17 return 0; 18 }