AcWing 11. 背包问题求方案数

题目传送门

本题求\(01\)背包的最佳方案数，那么定义两个数组：\(f[N]\),\(g[N]\)

\(f[i]\)用来存储背包容积为 \(i\) 时的最佳方案的总价值，

\(g[i]\)为背包容积为 \(i\) 时总价值为最佳的方案数。

先初始化所有的 \(g[i]\) 为 \(1\)，因为背包里什么也不装也是一种方案。

外层循环 \(n\) 次，每次读入新物品的 \(v\),\(w\)

求出装新物品时的总价值，与不装新物品时作对比

如果装新物品的方案总价值更大，那么用 \(f[j?v]+w\) 来更新 \(f[j]\)，用 \(g[j?v]\) 更新 \(g[j]\)

如果总价值相等，那么最大价值的方案数就多了 \(g[j?v]\) 种。

#include 

using namespace std;

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

int f[N];   //f[i]用来存储背包容积为i时的最大价值，
int g[N];   //g[i]用来存储背包容积为i时,获取到最大价值时的方案数

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    //先初始化所有的 g[i]为 1，因为背包里什么也不装也是一种方案,方案数最小是1
    for (int i = 0; i <= m; i++) g[i] = 1;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--) {
            //求出装新物品时的总价值，与不装新物品时作对比
            int value = f[j - v] + w;
            //如果装新物品的总价值更大，那么用f[j?v]+w来更新f[j](经典01背包)
            if (value > f[j]) {
                f[j] = value;
                //用g[j?v]更新g[j]
                g[j] = g[j - v];
            } else if (value == f[j])
                //如果总价值相等，那么最大价值的方案数就多了 g[j?v]种
                g[j] = (g[j] + g[j - v]) % MOD;
        }
    }
    printf("%d", g[m]);
    return 0;
}