分析
这道题目和上面的采药的区别仅仅在于，每个物品可以无限次的取，其他的和采药并没有什么区别。
当然，这样的问题仍然可以用背包模型来解决，我们将这种模型称为无限背包。
在这种情况下，我们可以把上面的opt[i-1,j-v[i]]变成opt[i,j-v[i]],即允许一种物品被取多次。
又由于是计数，所以应该有opt[i,j]:=opt[i,j-v[i]]+opt[i-1,j]。
还有一个优化就是我们可以把opt数组压缩成长度为total的一维数组（因为这样是不会影响结果的），可以极大地优化它的空间复杂度。
状态的确定
我们用opt[i]表示硬币总面值为i时共有多少种方法
Opt[i]:=opt[i]+opt[i-value[j]];(j=1,2,3..n)
代码
for i:=0 to total do opt[i]:=0;
opt[0]:=1;
for i:=1 to n do
for j:=a[i] to t do
opt[j]:=opt[j]+opt[j-a[i]];
writeln(opt[t]);
每个硬币都是无限的吗？
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024