背包问题求方案数（最大价值的方案数）思路：

100 阅读 0 评论 66 点赞

我是靠谱客的博主现实酸奶，这篇文章主要介绍背包问题求方案数（最大价值的方案数）思路：，现在分享给大家，希望可以做个参考。

原题链接

思路：

求最大价值的同时更新最大方案；
因为所有不放物品也算一种方案，所以初始化所有 $c n t [i] = 1$
如果 $f [j - v [i]] > f [j]$ 说明用当前物品的体积比不用当前物品的体积大，那就先更新最大价值，使 $f [j] = f [j - v [i]] + w [i]$ ，同时更新 $c n t [j]$ ，因为当前情况下，用前i个物品体积为j时，是通过用 $i - 1$ 个物品体积为 $j - v [i]$ 时加上当前这一件物品得来的，所以方案数就等于 $i - 1$ 个物品体积为 $j - v [i]$ 时的方案数，此时的方案数是 $f [j] = f [j - v [i]]$ .

如果 $f [j - v [i]] = = f [j]$ 说明用第 $i$ 种物品和不用第 $i$ 种物品价值一样，那么此时的方案数 $c n t [j]$ 就由用第i种物品的方案和不用第i种物品的方案加起来，因为都可以使体积为 $j$ ，所以当前的方案数是 $f [j] + = f [j - v [i]] .$

复制代码

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
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, mod = 1e9 + 7 ;
int v[N], w[N], f[N], cnt[N];

int main()
{
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; i ++ )
        {
                cin >> v[i] >> w[i];
        }
        for (int i = 0; i <= m; i ++ ) cnt[i] = 1;
        for (int i = 1; i <= n; i ++ )
        {
                for (int j = m; j >= v[i]; j -- )
                {
                        if (f[j - v[i]] + w[i] > f[j]) 
                        {
                                f[j] = f[j - v[i]] + w[i];
                                cnt[j] = cnt[j - v[i]];
                        }
                        else if (f[j] == f[j - v[i]] + w[i])
                        {
                                cnt[j] += cnt[j - v[i]];
                        }
                        cnt[j] %= mod;
                        
                }
        }
        cout << cnt[m] << endl;
        return 0;
}