【动态规划】背包问题求具体方案

题目

12. 背包问题求具体方案 - AcWing题库

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 $1 … N$ 。

输入格式

第一行两个整数， $N，V$ ，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$ ，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 $1 … N$ 。

数据范围

$0 \lt N, V \le 1000$
$0\lt v_i, w_i \le 1000$

输入样例

输出样例：

1 4

解题

方法一：动态规划

思路

本题要求最优解的具体方案，对于01背包其实就是求最优解中每个物品是否被选。

观察01背包问题的递推式： $f(i, j) = \max(f(i - 1, j), f(i - 1, j - v_i) + w_i)$ ，会发现 $f(i, j)$ 会从两项中选择较大者，其中前者对应的是不选物品 $i$ ，后者对应的是选择物品 $i$ 。所以是通过 $f(i)$ 与 $f(i - 1)$ 的关系来判断物品 $i$ 是否被选择的。

那么求具体方案的问题就可以类比为图论中最短路问题求具体路径：

求最优解具体方案其实就是在求图中走到了 $f(n, c)$ 的某条路径，那么结合上面的结论，对于01背包问题而言路径的建立是由最优解中某个物品是否被选决定的。

字典序最小的方案：

每个物品有三种可能：

$f(i-1, j) < \max(f(i-1, j - v_i) + w_i)$ ，只能选，则必须选。
$f(i-1, j) > \max(f(i-1, j - v_i) + w_i)$ ，不能选，则必不选。
$f(i-1, j) = \max(f(i-1, j - v_i) + w_i)$ ，可选可不选，则必须选。
（要保证字典序最小就要在前面物品能选的情况下优先选择前面的物品）

所以最终正确做法是：先按照 $n \to 1$ 的顺序反向求解01背包问题，然后按照 $1\to n$ 的顺序反推出每个物品是否选择，根据选择情况对应上面的三种可能，做出第二次选择（必选就输出，不选直接跳过）。

代码

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int c = (int) in.nval;
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            v[i]= (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        int[][] f = new int[n + 2][c + 2];
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j <= c; ++j) {
                f[i][j] = f[i + 1][j];
                if (v[i] <= j) f[i][j] = Math.max(f[i][j], f[i + 1][j - v[i]] + w[i]);
            }
        }
        int j = c;
        for (int i = 1; i <= n; ++i) {
            if (v[i] <= j && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
                System.out.print(i + " ");
                j -= v[i];
            }
        }
    }
}

二维数组记录方案：

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int c = (int) in.nval;
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            v[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        int[][] f = new int[n + 2][c + 2];
        boolean[][] g = new boolean[n + 1][c + 1];
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j <= c; ++j) {
                f[i][j] = f[i + 1][j];
                if (v[i] <= j) {
                    if (f[i + 1][j - v[i]] + w[i] >= f[i][j]) {
                        f[i][j] = f[i + 1][j - v[i]] + w[i];
                        g[i][j] = true;
                    }
                }
            }
        }
        int j = c;
        for (int i = 1; i <= n; ++i) {
            if (v[i] <= j && g[i][j]) {
                System.out.print(i + " ");
                j -= v[i];
            }
        }
    }
}

滚动数组优化（基于二维数组记录方案）：

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int c = (int) in.nval;
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            v[i] = (int) in.nval;
            in.nextToken();
            w[i] = (int) in.nval;
        }
        int[] f = new int[c + 2];
        boolean[][] g = new boolean[n + 1][c + 1];
        for (int i = n; i >= 1; --i) {
            for (int j = c; j >= v[i]; --j) {
                if (f[j - v[i]] + w[i] >= f[j]) {
                    f[j] = f[j - v[i]] + w[i];
                    g[i][j] = true;
                }
            }
        }
        int j = c;
        for (int i = 1; i <= n; ++i) {
            if (v[i] <= j && g[i][j]) {
                System.out.print(i + " ");
                j -= v[i];
            }
        }
    }
}

目录CONTENT

【动态规划】背包问题求具体方案

题目

解题

方法一：动态规划

思路

代码

评论区