python

1.6 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

背包问题-方案数-空间至少`j`

一、`01`背包

例子：给你一堆物品，每个物品有一定的体积，每个物品只能选一个，求 总体积至少是m 的 方案数

输入

3 5
2 3 7

输出

1、二维

#include <bits/stdc++.h>

using namespace std;
const int N = 110;

int n, m;
int f[N][N];

int main() {
    scanf("%d %d", &n, &m);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d", &v);
        for (int j = 0; j <= m; j++) //即使物品体积比j大，j - v < 0，也能选，等价于f[i - 1][0]
            f[i][j] = f[i - 1][j] + f[i - 1][max(0, j - v)];
    }
    printf("%d\n", f[n][m]);
    return 0;
}

2、一维

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int n, m;
int f[N];

int main() {
    scanf("%d %d", &n, &m);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d", &v);
        //即使物品体积比j大，j - v < 0，也能选，等价于f[0]
        for (int j = m; j >= 0; j--) f[j] += f[max(0, j - v)];
    }
    printf("%d\n", f[m]);
    return 0;
}

二、完全背包

例子：给你一堆物品，每个物品有一定的体积，每个物品可以选无数多个，求总体积至少是m的方案数 答案是无穷多种方案数,这么唠嗑没意义，因为每个物品随意选择，超过容量就行，那太容易了~

1.6 KiB Raw Permalink Blame History Unescape Escape

背包问题-方案数-空间至少j

一、01背包