背包问题_11.pdf

01背包求具体方案

AcWing 12. 背包问题求具体方案
01背包，不超过，取得最大价值的字典序最小的方案
题目描述
有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

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

数据范围
00<vi,wi≤1000

样例
输入：
4 5
1 2
2 4
3 4
4 6
输出：
1 4

思路：
要求输出字典序最小的方案，所以得倒着处理每一件物品进行DP，最后再正推求解具体方案。贪心，每个物品可选一定选，一定能保证解为最小字典序。
不能用一维减小空间开销，因为中间过程是我们求解方案的关键。

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 1010;
  5.     static int[][] f = new int[N][N];
  6.     static int n, m;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         n = sc.nextInt();
  10.         m = sc.nextInt();
  11.         int[] v = new int[n + 1], w = new int[n + 1];
  12.         for (int i = n; i > 0; i--) {
  13.             v[i] = sc.nextInt();
  14.             w[i] = sc.nextInt();
  15.         }
  17.         for (int i = 1; i <= n; i++) {
  18.             for (int j = 0; j <= m; j++) {
  19.                 f[i][j] = f[i - 1][j];
  20.                 if (j >= v[i]) {
  21.                     f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
  22.                 }
  23.             }
  24.         }
  26.         int j = m;
  27.         for (int i = n; i > 0; i--) {
  28.             if (j >= v[i] && f[i - 1][j - v[i]] + w[i] == f[i][j]) {
  29.                 System.out.print((n - i + 1) + " ");
  30.                 j -= v[i];
  31.             }
  32.         }
  33.     }
  34. }

完全背包求具体方案

1449. 数位成本和为目标值的最大数字
完全背包，恰好，取得最大价值的最优方案（最优用到贪心的思想）

分组背包求具体方案

AcWing 1013. 机器分配
分组背包，每组可选[0, m]个物品，选择的总物品数不超过提供的总物品数，取得最大价值的任意一种方案