01背包求方案数

总体积等于背包容积

原理

见《进阶指南》第277页。

模板题

AcWing-278-数字组合

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = 10010;
int n, m;
int a[N], f[M];

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    f[0] = 1;
    for (int i = 1; i <= n; ++ i)
        for (int j = m; j >= a[i]; -- j)
            f[j] += f[j - a[i]];
    cout << f[m] << endl;
    return 0;
}

总体积不超过背包容积

模板题

AcWing-11-背包问题求方案数

#include <iostream>
using namespace std;

const int N = 1010, M = 1e9 + 7;
struct node {
    int v, w;
};
int n, m;
node a[N];
int f[N], c[N];

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> a[i].v >> a[i].w;

    for (int i = 0; i <= m; ++ i) c[i] = 1; // 什么也不装
    for (int i = 1; i <= n; ++ i) {
        int v = a[i].v, w = a[i].w;
        for (int j = m; j >= v; -- j) {
            int val = f[j - v] + w;
            if (val == f[j])
                c[j] = (c[j] + c[j - v]) % M;
            else if (val > f[j]) {
                f[j] = val;
                c[j] = c[j - v];
            }
        }
    }
    cout << c[m] << endl;
    return 0;
}