货币系统

完全背包问题 + 方案数求解

1.$f[i,j]$的含义

$f[i,j]$代表的是从前i种货币中取若干个出来，最后凑出价值为j的方案数

2.状态转换

对于第i种货币，我们一共有两种策略，即拿，或者不拿

①不拿第i种货币：
这种情况下$f[i,j]$ = $f[i-1,j]$，其中$[i-1,j]$代表的含义为从前i-1种货币中取若干个出来，最后凑出价值为j的方案数
②拿第i种货币：
这种情况下，就存在很多种情况，例如我只拿一张第i个货币，我只拿两种第i个货币，…，拿了N种第i个货币，转换为表达式即为$f[i,j] = f[i-1,j-v[i]] + f[i-1,j-2v[i]] + … + f[i-1,j-nv[i]]$

综上所述，可以得到状态转移方程为：

f[i,j] = f[i-1,j] + f[i-1,j-v[i]] + f[i-1,j-2v[i]] + ... + f[i-1,j-nv[i]]

考虑下$f[i,j-v[i]]$，其代表的含义是从前i-1种货币中取若干个出来，最后凑出价值为j-v[i]的方案数

同理我们按照上述的思路去看，有两种取法：

①不拿第i种货币：
这种情况下$f[i,j-v[i]]$ = $f[i-1,j-v[i]]$，其中$[i-1,j-v[i]]$代表的含义为从前i-1种货币中取若干个出来，最后凑出价值为j-v[i]的方案数
②拿第i种货币：
这种情况下，就存在很多种情况，例如我只拿一张第i个货币，我只拿两种第i个货币，…，拿了N种第i个货币，转换为表达式即为$f[i,j] = f[i-1,j-2v[i]] + f[i-1,j-3v[i]] + … + f[i-1,j-(n+1)v[i]]$

综上所述，可以得到状态转移方程为：

f[i,j-v[i]] = f[i-1,j-v[i]] + f[i-1,j-2v[i]] + f[i-1,j-3v[i]] + ... + f[i-1,j-(n+1)v[i]]

因为n是无穷的，所以n和n+1可以近似看为是一样的

最终，我们得到如下两个递推关系式：

①f[i,j] = f[i-1,j] + f[i-1,j-v[i]] + f[i-1,j-2v[i]] + ... + f[i-1,j-nv[i]]

②f[i,j-v[i]] = f[i-1,j-v[i]] + f[i-1,j-2v[i]] + f[i-1,j-3v[i]] + ... + f[i-1,j-(n+1)v[i]]

可以发现②是①式的一部分，可以最后归纳出f[i,j] = f[i-1,j] + f[i,j-v[i]]的结论

故有了最后的递推关系式：

f[i,j] = f[i-1,j] + f[i,j-v[i]]

基于完全背包问题的优化思路，我们可以将其优化成为一维状态转移

即有了如下的表达

for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            if(j >= v[i])
                d[j] = d[j] + d[j - v[i]];

解题代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 10010;

int n, m;
int v[N];
LL d[N];

int main()
{
    d[0] = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ )
        scanf("%d", &v[i]);
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            if(j >= v[i])
                d[j] = d[j] + d[j - v[i]];
    printf("%lld", d[m]);
    return 0;
}