货币系统（求方案数的背包）

---

货币系统

给你一个$n$种面值的货币系统，求组成面值为$m$的货币有多少种方案。

输入格式
第一行，包含两个整数$n$和$m$。

接下来$n$行，每行包含一个整数，表示一种货币的面值。

输出格式
共一行，包含一个整数，表示方案数。

数据范围
$n\le 15,m\le 3000$

输入样例：

3 10
1
2
5
1
2
3
4

输出样例：

10
1

---

首先，可以将货币看成是一种背包，背包的容量为m，再细想可以发现各种面值的货币是无限的，所以这显然是一个完全背包问题，但与传统背包不同的是，这里要求解的不再是最大价值，而是方案的个数。

因此，状态表示和转移方程都会有点变化。
首先是状态表示：记f[i][j]：在前i种货币里面选，凑成j元钱的方案数；那么目的就是要求f[n][m]。

然后是转移方程：
还是引用的原版完全背包问题里那个 “退一步而求其之” 的思路，即

那么在这里第i个货币，其面值为v：不选或是选择k张来凑成一个新方案。
只不过这里不同于上式对方案取一个max，而是计算方案的总和，所以是进行相加。

即$f(i,j)=\Sigma f(i-1,j-k\times v),k\in [0,]$

不过这样相加太慢了，所以有一个等式的变形，如下所示：

红框内都是相等的，所以只需用$f(i,j-v)$替换便可以得到：
最终的转移方程即为：
f[i]f[j] = f[i - 1][j] + f[i][j - v]。

C++代码

首先是二维的：

#include 
#include 
using namespace std;
typedef long long ll;

const int N = 3010;

int n, m;
ll f[20][N];

int main(){
    cin >> n >> m;
    f[0][0] = 1;        //初始化，啥都没凑出来是一种方案
    for(int i = 1;i <= n;i ++){
        int v;
        cin >> v;
        
        for(int j = 0;j <= m;j ++){
            f[i][j] = j >= v ? f[i - 1][j] + f[i][j - v] : f[i - 1][j];
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

再根据上面的代码做等价变形，优化至一维，
观察，可以看到当维护到f[i][j]的时候，需要有上一轮即i - 1层循环时的f[i - 1][j] + 在这一轮即i层循环时的f[i][j - v]。
所以一维优化中j的循环顺序要从小到大(v—>m)地进行，这样保证了滚动数组数据的对应（读f[j]时f[j - v]注定被本层循环更新过了）。

#include 
#include 
using namespace std;
typedef long long ll;

const int N = 3010;

int n, m;
ll f[N];

int main(){
    cin >> n >> m;
    f[0] = 1;        //初始化，啥都没凑出来是一种方案
    for(int i = 1;i <= n;i ++){
        int v;
        cin >> v;
        
        for(int j = v;j <= m;j ++){
            f[j] += f[j - v];
        }
    }
    
    cout << f[m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

数字组合（需注意数量上的区别）

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

输入格式
第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示 A1,A2,…,AN。

输出格式
包含一个整数，表示可选方案数。

数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。

输入样例：

4 4
1 1 2 2
1
2

输出样例：

3
1

---

这个问题乍一看似乎跟上述的好像是同一个问题，但细想一下就知道差别体现在了现在这个问题的每种货币只有一个（虽然有些可能会相同），而不是可以无限地挑选，所以它就回归到的是0 - 1背包问题。

假设状态表示还是跟上面一样的。
那么对于第i件货币，
就只有两个选择了：

• 不选i：f[i][j] = f[i - 1][j]，
• 选i：f[i][j] = f[i - 1][j - A[i]]。

归结起来，状态转移方程就是：
f[i]f[j] = f[i - 1][j] + f[i - 1][j - v]。

二维代码不用说了，一维此时相较于上面的货币系统，变化体现在j循环上，因为方程右边都是i - 1层循环下的状态，所以此时j的遍历需要逆序（从m到v）遍历。

C++代码

#include 
using namespace std;

const int N = 100010;

int f[N];
int n, m;

int main(){
    cin >> n >> m;
    f[0] = 1;       //初始化，空集是一种方案
    
    for(int i = 1;i <= n;i ++){
        int v;
        cin >> v;
        
        for(int j = m;j >= v;j --){
            f[j] = f[j] + f[j - v];
        }
    }
    
    cout << f[m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24