USACO/money

分析

背包问题

设dp[i,j]表示前i种货币构成j的方法数，用cc记录货币的面值，状态转移方程为：

dp[i,j]=dp[i-1,j];    不用第i种货币
dp[i,j]=dp[i-1,j]+dp[i,j-cc[i]]    用第i种货币，j>=cc[i]

时间复杂度是O(VN)的，如果把面值相同的货币记做一种，可以更快一些。 参见dd牛的《背包9讲》

---

可以优化得在空间上更好些。

        for i:=1 to v do
                for j:=0 to n-w[i]do
                        inc(f[j+w[i]],f[j]);

f[i]表示构成i所有的方法数。输出f[n]即可

---

完全背包问题（数量不限）

begin
dp[0]:=1;
 
for i:=1 to n do
   begin
     read(a);
     for j:=a to m do
         inc(dp[j],dp[j-a]);
   end;
writeln(dp[m]);
end.
{就搞定了,空间再优}

jzoi

分析2

生成函数（母函数）

也许麻烦了点，但也是一种方法。

原问等价于求一个形如a1X1+a2X2+...+avXv=n的方程的非负整数解的个数。构造生成函数f(x)=(x^0+x^a1+x^(2*a1)+x^(3*a1)+...)(x^0+x^a2+x^(2*a2)+x^(3*a2)+...)...(x^0+x^av+x^(2*av)+x^(3*av)+...) 则x^n的系数就是所求。

分析3

Kind[ i ]表示硬币种类，Dp[ j ] 表示 取用面值为j的硬币的方式 考虑最后一种情况：总值为j元，取用了第 i 种硬币，则子问题为取用j - Kind[ i ]元的方式，即Dp[ j-Kind[i] ]. 得到转移方程：Dp[ j ] = Dp[ j ] + Dp[ j-Kind[i] ];（j >= Kind[ i ]）,最后输出Dp[ N ]即可。

参考代码

C
C++
Pascal
Java

引用

[1]

[2]