一个acm找零钱问题
输入一个C，再输入N个不同面值的纸币
组合成C，求出所用纸币的张数最少的张数
比如：
C=100,N=5
有5个不同的面值，1，5，20，80，90
最后输出的结果为2
哪位高手指点指点
[解决办法]
这是俺AC的代码:
/**
&# tju2768.cpp
@author Eastsun
@version 1.0 2007/9/7
算法描述(动态规划):
记 coins[1,..,N]为N种可用的硬币面值,
min(c,k) 表示将总值为c的钱数用coins[1,..,k]来表示最少需要多少硬币,如果不能表示,则为无穷大
则有:
min(0,k) = 0; k>=0
min(c,0) = 无穷大, c>0
min(c,k) = min{min(c,k-1),min(c-coins[k],k)+1,...,min(c-i*coins[k],k)+i }
*/
#include<iostream>
const int MAX_C = 1000;
const int MAX_N = 10;
int min[MAX_C+1][MAX_N+1];
int coins[MAX_N+1];
int C,N;
int main(){
std::cin>>C>>N;
for(int index =1;index<=N;index++) std::cin>>coins[index];
for(int c =1;c<=C;c++) min[c][0] =C+1;
for(int n =1;n<=N;n++)
for(int c=1;c<=C;c++){
min[c][n] =min[c][n-1];
for(int k=1;k*coins[n]<=c;k++)
if(min[c][n]>min[c-k*coins[n]][n]+k) min[c][n] = min[c-k*coins[n]][n]+k;
}
std::cout<<min[C][N]<<std::endl;
}
