拼歌单 – 多重背包转01背包

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

题目来源，解法来源

有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。

输入描述:

每个输入包含一个测试用例。 每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。 接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。

输出描述:

输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对1000000007取模的结果。

示例1

输入

5 2 3 3 3

输出

9

换个更广泛的描述，有m首歌，长度不一，要拼成n长的歌单，每首只出现一次，怎么办，这就是有m件物品，背包大小为n的01背包问题。

这里是两种长度的歌，每首歌不同，那么可以直接把它们展开，变成X+Y首歌，组成K长的歌单，以示例进行描述：

歌曲长度	K= 1	2	3	4	5
2
2
2
3
3
3

我们就是填这种动态规划的表，按照动态规划的套路：

vector<int> songs{ 2, 2, 2, 3, 3, 3 };
vector<vector<int>> dp(6 + 1, vector<int>(5 + 1, 0));
dp[0][0] = 1;
for (int i = 1; i < dp.size(); ++i) {
	for (int j = 0; j < dp[i].size(); ++j) {
		if (j >= songs[i - 1]) {
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - songs[i - 1]];
		}
		else
		{
			dp[i][j] = dp[i - 1][j];
		}
	}
}
return dp[6, 5];

得到的dp为：

// 第一列没用，主要是为了统一运算逻辑，能装下当前值的时候加1
1 0 0 0 0 0		// 这一层没用，主要是为了统一运算逻辑，不用判断边界
1 0 1 0 0 0
1 0 2 0 1 0
1 0 3 0 3 0
1 0 3 1 3 3
1 0 3 2 3 6
1 0 3 3 3 9

由于每一行只计算一次，且后一行和这一行有直接对应的关系，因此可以只用一行的存储空间：

vector<int> dp(5 + 1);
dp[0] = 1;
for (int i = 0; i < 6; i++) {
	for (int j = 5; j >= songs[i]; j--) {
		dp[j] = (dp[j] + dp[j - songs[i]]);
	}
}
cout << dp[k];

得到：

1 0 3 3 3 9