转自
http://www.cnblogs.com/qiufeihai/archive/2012/09/11/2680840.html
首先说没限制的硬币问题吧:
先看这个问题：在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
我们用dp[n]表示用这些硬币组成n的方法总数。。。。
然后随着硬币种类的增加来更新dp[]的值，也就是最外面的一层循环for(i :1-->3)开始初始化的时候没有硬币，然后新来了面值为1的硬币，接着又来了面值为2的硬币。。。。
显然，每新增加一种面值的硬币，dp[]的值一定在增加。。。新的dp[] = 未新增前的dp[] + dp[1件新增硬币] + dp[2件新增硬币] + dp[3件新增硬币] +.......
dp[k件新增硬币]
由于for里用了完全背包里的顺序，for(j = c[i]; j <= n; j++)，所以dp[j] += dp[j - c[i]];中的dp[j - c[i]]已经是有k件新增硬币的状态了。。。。。
即j不停地向右，开始的时候得到只有一个新增硬币而组成n的总数，然后由只有1个新增硬币的结果得到只有2个新增硬币而组成n的总数，慢慢地,。。。。得到由越来越多件新增硬币组成n的总数得到的dp[i]就是该容量下的总数了
HDU 1284 : http://acm.hdu.edu.cn/showproblem.php?pid=1284
代码：
复制代码
#include <iostream>
using namespace std;
const int M = 32768 + 10;
int dp[M];
int main()
{
int n;
while (~scanf("%d", &n))
{
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= 3; i++)
{
for (int j = i; j <= n; j++)
{
dp[j] += dp[j - i];
}
}
printf("%d
", dp[n]);
}
return 0;
}
复制代码
HDU 1028 http://acm.hdu.edu.cn/showproblem.php?pid=1028
代码：
复制代码
#include <iostream>
using namespace std;
const int M = 120 + 10;
int dp[M];
int main()
{
int n;
while (~scanf("%d", &n))
{
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
dp[j] += dp[j - i];
}
}
printf("%d
", dp[n]);
}
return 0;
}
复制代码
HDU 1398 http://acm.hdu.edu.cn/showproblem.php?pid=1398
代码：
复制代码
#include <iostream>
#include <cmath>
using namespace std;
const int M = 300 + 10;
int dp[M];
int main()
{
int n;
while (~scanf("%d", &n), n)
{
memset(dp, 0, sizeof(dp));
dp[0] = 1;
int max = (int)sqrt(n * 1.0);
for (int i = 1; i <= max; i++)
{
for (int j = i * i; j <= n; j++)
{
dp[j] += dp[j - i * i];
}
}
printf("%d
", dp[n]);
}
return 0;
}
复制代码
接着是有总数限制的硬币问题如HDU 2069 http://acm.hdu.edu.cn/showproblem.php?pid=2069
他要求硬币总数不超过100
这时候我们就要增加一个维度来限制数量，dp[i][j]表示用不超过i个硬币组成j的总数
最外一层枚举硬币总类和上面一样的道理，dp[num][j] += dp[num - 1][j - c[i]]这里是对于新来的每一个硬币，= 放这个硬币的总数+不放这个硬币的总数，
d[num-1][j-c[i]]是之前已经更新到有k-1个新硬币的了，而这个式子只针对地k个新硬币所以num-1是未放这个新硬币之前的答案,即dp[j - c[i]]放的都只是放一个硬币
（第k个新硬币）得到的总数
然后答案要累加不超过i:0-->100得到的总数,一定要从0开始累加，因为数据有0个硬币的总数
代码：
复制代码
#include <iostream>
#include <cmath>
using namespace std;
const int M = 300 + 10;
int dp[111][M];
int c[] = {0, 1, 5, 10, 25, 50};
int main()
{
//freopen("in.txt", "r", stdin);
int n;
while (~scanf("%d", &n))
{
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= 5; i++)//枚举硬币总类
{
for (int num = 1; num <= 100; num++)//枚举硬币个数
{
for (int j = c[i]; j <= n; j++)//枚举容量
{
dp[num][j] += dp[num - 1][j - c[i]];
}
}
}
int ans = 0;
for (int i = 0; i <= 100; i++)//累加答案
{
ans += dp[i][n];
}
printf("%d
", ans);
}
return 0;
}