最少硬币问题
最少硬币问题 动态规划 C++
【问题描述】有n种不同面值的硬币，各硬币面值存于数组T[1:n];现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。
【编程任务】对于给定的1<=n<=10，硬币面值数组、各面值的个数及钱数m，0<=m<=2001，编程计算找钱m的最少硬币数。
input : 第一个数字n,后面n行每行两个数，面值T[i],面值个数Num[i];最后是钱数m。
output：最少硬币数。
Sample intput :
3
1 3
2 3
5 3
18
Sample output:
5
我不是问这个题怎么解 我是想问
输入的参数中
1 3
2 3
5 3
都代表什么意思
帮忙解释一下
[解决办法]
若用动态规划的话，
设f(i,Si)表示在剩余钱数为i，以及剩余硬币的状态为Si时的最小硬币组合数。
Si在最开始可以表示为（3，3，3），各个硬币的数量各三个。
若当前Si=(m,n,p)
f(i,Si) = min(
f(i-5, Si1) (i>5, Si1=(m-1,n,p)),
f(i-2, Si2) (i>2, Si2=(m,n-1,p)),
f(i-1, Si3) (i>1, Si3=(m,n,p-1)),
) + 1
[解决办法]
f[v,i]表示前i个物品装满容量v所需最小数目 所求为f[m,n]
f[v,i]=min{f[v,i-1],k+f[v-kT[i],i-1]},k=1...Num[i] 且v> =kT[i]
这个地方要对Num[i]优化也可以，只不过很麻烦
