题目描述
经过七七四十九天,
终于……
我学会了方案背包!
但是……
。。。咳咳!
一时高兴,写了一些忘乎所以的废话,
不要在意哈。
样例
打表就能过的东西,
要了干什么?
时间复杂度
$O(NV)$
C++ 代码
注意!!!题目上写的是最优的方案!
不是装满的方案!
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int N, V, u, w, f[1005], a[1005], t, c, res;
int main() {
cin >> N >> V;
a[0] = 1;
for (int i = 0; i < N; i++) {
cin >> u >> w;
for (int j = V; j >= u; j--) {
t = max(f[j], f[j - u] + w), c = 0;
if (t == f[j])
c = a[j] % mod;
if (t == f[j - u] + w)
c = (c + a[j - u]) % mod;
f[j] = t;
a[j] = c;
}
}
for (int i = 0; i <= V; i++)
if (f[i] == f[V])
res = (res + a[i]) % mod;
cout << res << endl;
return 0;
}
解释
之前求最大价值,我们用的是一维数组$f$
那么就再加一维数组$a$,存放方案数。
一旦$f_i$与最大价值$f_V$相等,那么$a_i$就要加进方案数中。