题目大意:
给定 $N$ 个正整数 $A_1, A_2, … , A_N$ ,从中选出若干个数,使它们的和为 $M$,求有多少种选择方案。
解题方法:
我们很容易发现这道题考察到了两个知识点:背包问题求方案数,背包问题体积刚好。
那么我们先看这两个问题,再来看这道题。
背包问题求方案数
就是求01背包最优解的方案数。
这道题 $f[i][j]$ 有两种表示方式,对应两种不同的代码。
下面是第一种,$f[i][j]$ 表示考虑前 $i$ 个物品,总体积 恰好 为 $j$ 的方案数。
这就引出了我们又一种表示方式,之前都是不超过,这回变成了 恰好。那么初始化就需要做一些改变。
那我们需要从定义入手。
首先一开始所有的状态都还没被遍历过,不知道合不合法,所有都要初始化为 $-INF$。
然后所有考虑前 $i$ 个物品,总体积不超过0的方案都是合法的,但是价值都是0,所以这些都是0。
如果一维就是f[0] = 1
。
完整代码,时间复杂度:$O(nm)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int v[N], w[N];
int f[N][N], g[N][N];
//g[i][j]就是方案数。
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
memset(f, -0x3f, sizeof f);
//这一句话在这里(只有在特殊情况下)可以不要,因为只有在体积=0时才会有方案,所以可以省去。
for (int i = 0; i <= n; i ++ ) g[i][0] = 1, f[i][0] = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
if (f[i - 1][j] >= f[i - 1][j - v[i]] + w[i]) g[i][j] = (g[i][j] + g[i - 1][j]) % mod;
if (f[i - 1][j] <= f[i - 1][j - v[i]] + w[i]) g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % mod;
//从哪里转移过来就加上哪里,如果相等就一起加上。
//if (g[i][j] == 0) g[i][j] = 1; 不能有这句,因为没有的话就说明无法构成,不能赋值为1!!!
}
else g[i][j] = g[i - 1][j] % mod;
}
}
int sum = 0, res = 0;
for (int i = 1; i <= m; i ++ )
if (f[n][i] > f[n][res]) { //找到价值最大的下标
res = i;
}
for (int i = m; i >= 0; i -- ) {//最后必须求是答案的和!!!
if (f[n][i] == f[n][res]) { //所有能凑出最大值的和
sum += g[n][i];
}
}
cout << sum << endl;
return 0;
}
还有一种方法,就是f[i][j]表示小于等于j的最大价值,这样也可以做。
完整代码,时间复杂度:$O(nm)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int v[N], w[N];
int f[N][N], g[N][N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
g[i][j] = 1;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
if (f[i - 1][j] > f[i - 1][j - v[i]] + w[i]) g[i][j] = g[i - 1][j] % mod;
else if (f[i - 1][j] < f[i - 1][j - v[i]] + w[i]) g[i][j] = g[i - 1][j - v[i]] % mod;
else g[i][j] =(g[i - 1][j - v[i]] + g[i - 1][j]) % mod;
}
else g[i][j] = g[i - 1][j] % mod;
}
}
cout << g[n][m] << endl;
return 0;
}
这一道题已经解释了所以问题,我们可以直接把数字转成体积,然后我们要价值为 $m$,所以数字也是价值。
然后就可以直接解决了。
$$闫氏DP分析法$$
- 状态表示——集合:$f[i][j]$ 表示考虑前 $i$ 个数字,且总数字和刚好是 $j$ 的集合下能获得的方案数。
- 状态表示——属性:因为是求方案数,故为 $count$,也就是和。
- 状态计算——集合划分:考虑第 $i$ 个数选不选。
- 不选或选不了(剩余数量不够 $j < a[i]$):$f[i - 1][j]$。
- 选:$f[i - 1][j - a[i]] + a[i]$。首先你对第i个数字进行了你的抉择,所以前一维变成了 $i - 1$,接着因为使用了 $a[i]$ 的数字,所以应该是 $j - a[i]$。
这样就完事了。
完整代码,时间复杂度:$O(nm)$
#include <iostream>
using namespace std;
const int N = 10010;
int n, m;
int f[N];
int main() {
cin >> n >> m;
f[0] = 1;
for (int i = 1; i <= n; i ++ ) {
int a;
cin >> a;
for (int j = m; j >= a; j -- ) f[j] += f[j - a];
}
cout << f[m] << endl;
return 0;
}
背包问题求的是最大价值,这个问题求方案数,怎么看成一样的呢
你就把方案数看成价值就行了
看成价值为什么累加就可以了啊
因为方案数就是累加而来的