背包问题求方案数

题目链接：背包问题求方案数

01背包

时间复杂度O(nm)

本题求01背包的最佳方案数，那么定义两个数组：f[N],cnt[n]
f[i]用来储存背包容积为i时的最佳方案的总价值
cnt[i]为背包容积为i时总价值为最佳的方案数

先初始化所有的cnt[i]为1，因为背包里什么也不装也是一种方案
外层循环n次，每次读入新物品大的v,w
求出装新物品时的总价值，与不装新物品时做对比
如果装新物品的方案总价值更大，那么用f[j-v]+w来更新f[i]，用cnt[j-v]更新cnt[j]
如果总价值相等，那么最大价值的方案数就多了cnt[j-v]种

#include<iostream>

using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;

int f[N], cnt[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= m; i ++)  cnt[i] = 1;

    for(int i = 1; i <= n; i ++)
    {
        int v, w;
        scanf("%d%d", &v, &w);
        for(int j = m; j >= v; j --)
        {
            int value = f[j - v] + w;
            if(value > f[j])
            {
                f[j] = value;
                cnt[j] = cnt[j - v];
            }else if(value == f[j]){
                cnt[j] = (cnt[j] + cnt[j - v]) % mod;
            }
        }
    }

    printf("%d", cnt[m]);
    return 0;
}

作者：滑稽_ωﾉ
链接：https://www.acwing.com/solution/content/3999/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。