【模板】01背包

思路

经典的 01 背包模板题，但这道题要求输出两个答案：

  1. 不要求装满：背包容量为 ，在不超过容量的前提下，能装的最大价值是多少？
  2. 恰好装满：背包容量恰好为 时，能装的最大价值是多少？如果装不满就输出 0。

01 背包基础

01 背包的核心：每个物品只有「选」或「不选」两种状态。

定义 表示容量为 时能获得的最大价值。对于每个物品 ，从大到小遍历容量（这样保证每个物品只选一次）：

$$

两问的区别在于初始化

这道题的精髓就在初始化：

第一问（不要求装满）： 全部初始化为 0。因为任何容量下，「什么都不装」也是一种合法方案，价值为 0。

第二问（恰好装满）：只有 是合法的（容量为 0 恰好装满），其余 初始化为 （或 ），表示这些状态目前不可达。转移时只从合法状态（）转移过来，这样最终 就说明无法恰好装满。

为什么这样就能保证「恰好装满」？因为初始时只有 是合法起点，所有的状态都是从 一步步转移来的，每一步都恰好用掉了对应的体积，所以 合法就意味着存在一组物品体积之和恰好等于 。

复杂度

  • 时间复杂度：
  • 空间复杂度：（滚动数组优化）

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, V;
    scanf("%d%d", &n, &V);
    vector<int> v(n), w(n);
    for(int i = 0; i < n; i++) scanf("%d%d", &v[i], &w[i]);

    // dp1: 不要求装满
    vector<int> dp1(V+1, 0);
    // dp2: 恰好装满，-1 表示不可达
    vector<int> dp2(V+1, -1);
    dp2[0] = 0;

    for(int i = 0; i < n; i++){
        for(int j = V; j >= v[i]; j--){
            dp1[j] = max(dp1[j], dp1[j - v[i]] + w[i]);
            if(dp2[j - v[i]] >= 0){
                dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);
            }
        }
    }

    printf("%d\n", dp1[V]);
    printf("%d\n", dp2[V] < 0 ? 0 : dp2[V]);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        int[] v = new int[n], w = new int[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            v[i] = Integer.parseInt(st.nextToken());
            w[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp1 = new int[V + 1]; // 不要求装满
        int[] dp2 = new int[V + 1]; // 恰好装满
        Arrays.fill(dp2, -1);
        dp2[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = V; j >= v[i]; j--) {
                dp1[j] = Math.max(dp1[j], dp1[j - v[i]] + w[i]);
                if (dp2[j - v[i]] >= 0) {
                    dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
                }
            }
        }

        System.out.println(dp1[V]);
        System.out.println(dp2[V] < 0 ? 0 : dp2[V]);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, V = map(int, input().split())
    items = []
    for _ in range(n):
        vi, wi = map(int, input().split())
        items.append((vi, wi))

    dp1 = [0] * (V + 1)
    dp2 = [-1] * (V + 1)
    dp2[0] = 0

    for vi, wi in items:
        for j in range(V, vi - 1, -1):
            if dp1[j - vi] + wi > dp1[j]:
                dp1[j] = dp1[j - vi] + wi
            if dp2[j - vi] >= 0:
                val = dp2[j - vi] + wi
                if val > dp2[j]:
                    dp2[j] = val

    print(dp1[V])
    print(dp2[V] if dp2[V] >= 0 else 0)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
    const [n, V] = lines[0].split(' ').map(Number);
    const v = [], w = [];
    for (let i = 1; i <= n; i++) {
        const parts = lines[i].split(' ').map(Number);
        v.push(parts[0]);
        w.push(parts[1]);
    }

    const dp1 = new Array(V + 1).fill(0);
    const dp2 = new Array(V + 1).fill(-1);
    dp2[0] = 0;

    for (let i = 0; i < n; i++) {
        for (let j = V; j >= v[i]; j--) {
            dp1[j] = Math.max(dp1[j], dp1[j - v[i]] + w[i]);
            if (dp2[j - v[i]] >= 0) {
                dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
            }
        }
    }

    console.log(dp1[V]);
    console.log(dp2[V] < 0 ? 0 : dp2[V]);
});