本文共 1848 字，大约阅读时间需要 6 分钟。
给定面值为1,5,10,20,50的零钱，给定一个金额A，求组合成A的方法的数量
假定一个面额为x,则组合为A的方法数目 = 不使用x面额的零钱组合成A的方法的数量 + 使用任何面值的零钱组合成A -x的方法的数量
可以看成两类，一类是没有面额x而组合成A的数量，另一类是至少用一张面值为x而组合成A的方法的数量
直接按照算法的描述,递推关系应该是:
nway[v][n]=nway[v-1][n]+nway[v][n-coin[v]];
面额存储为coin= { 1,5,10,20,50},下标为v，给定的金额为n
使用任何0-v面额的零钱，组合成n的方法数量 = 使用任何0-(v-1)面额的零钱组合成n的方法数量 + 使用任何0-v面额零钱组合成n-coin[v]的数量
动态规划的递推式
for(i=0;i<=N;++i)
nway[0][i] = 1;//只用一种面额的零钱，对于任何N，方法都只有一种
for(i=0;i<5;++i)
nway[i][0] = 1;//如果N=0，方法也只有一种，就是不出任何零钱
for(v=1;v<5;++v)
{
for(n = coin[v];n<=N;++n)
{
nway[v][n]=nway[v-1][n]+nway[v][n-coin[v]];
}
}
由于nway[v-1][n]只会用一次，所以可以合并nway[v][n]=nway[v-1][n]
nway[0] = 1
for(v=0;v<5;++v)
for(n = coin[v];n<=N;++n)
nway[n] +=nway[n-coin[v]];//（可以扩展为nway[n] = nway[n] + nway[n-coin[v]]）其中第二个nway[n]可以看做是当v-1时的方法数目
由题目可知，coin可以是任何顺序，结果不变
//
上面的思路没错，但是程序写错了
解法1：可以出来金额为12,16这样的不能完全凑整的
const int N = 45;//钱总数const int K = 2;//钱的种类int main(){ int nway[K][N+1]; memset(nway,0,sizeof(nway)); int coin[]= {5,10}; int i; for(i=coin[0];i<=N;++i) nway[0][i] = 1;//只用一种面额的零钱，对于任何N，方法都只有一种 for(i=0;i 解法2：貌似这个更容易理解
int nway[N+1]; memset(nway,0,sizeof(nway)); int coin[]= {5,10,20}; nway[0] = 1; for (int i=0;i 上面的算法有瑕疵，就是如果输入43
，按照题目的意思应该得0，但是上面的程序会输出一个40的所有组合
int nway[N+1]; memset(nway,0,sizeof(nway)); int coin[]= {5,10,20}; nway[0] = 1; for (int i=0;i再重新解释下程序，nway[v]是在0到i-1种货币下，组合成v面额的数量；那在0到i种货币下，组合成面额v的方案的数量为=不含有第i种货币的组合方案数量+至少含有一张第i种货币的组合方案数量 其中nway[v-coin[i]]
表示0到i种货币组成面额为v-coin[i]的方案的数量，可能含有i货币也可能不含有，但是我们预留一个coin[i]的位置，也就使得至少有一张i货币； 经过多方论证，用一维nway正好，如果用二维的，就回出错。在网上看到另外一种算法：
假设a*1 + b*2 + c*5 = 100;非常容易看出c的循环次数最小，那么枚举c开始
c=0, a的取值为100,98,96,94,...,4,2,0
c=1,a的取值为95,93,91,89,...,5,3,1
c=2,a的取值为90,88,86,...,4,2,1
c=3,a的取值为85,83,81,...,5,3,1
.....
c=19,a的取值为5,3,1
c=20,a的取值0
现在看出规律了吧，100以内的偶数+95以内的奇数+90以内的偶数+。。。+5以内的奇数+0以内的偶数
我们可以立即写好如下程序：
for(int i = 0; i <= 100; i += 5)
{
sum += (m>>1) + 1;
}
转载地址：http://vfeti.baihongyu.com/