背包问题_7.pdf

9. 分组背包问题

分组背包，每组最多选一个，不超过总体积，最大价值
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：

  • 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
  • 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式
输出一个整数，表示最大价值。
数据范围
000输入样例

  1. 3 5
  2. 2
  3. 1 2
  4. 2 4
  5. 1
  6. 3 4
  7. 1
  8. 4 5

输出样例：

  1. 8

:::tips 分组背包可以看成特殊的多重背包 :::

二维版本

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

一维版本

  1. import java.util.*;
  3. public class Main {
  4.     static int N = 110;
  5.     static int[] f = new int[N];
  6.     static int n, m;
  7.     static int[] v = new int[N], w = new int[N];
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         n = sc.nextInt();
  11.         m = sc.nextInt();
  13.         for (int i = 1; i <= n; i++) {
  14.             int t = sc.nextInt();
  15.             for (int j = 0; j < t; j++) {
  16.                 v[j] = sc.nextInt();
  17.                 w[j] = sc.nextInt();
  18.             }
  20.             for (int j = m; j >= 0; j--) {
  21.                 for (int k = 0; k < t; k++) {
  22.                     if (j >= v[k])
  23.                         f[j] = Math.max(f[j], f[j - v[k]] + w[k]);
  24.                 }
  25.             }
  26.         }
  27.         System.out.println(f[m]);
  28.     }
  29. }

其它例题：

AcWing 1013. 机器分配
分组背包，每组可选[0, m]件物品，不超过总物品数，取得最大价值的任意方案
AcWing 487. 金明的预算方案
分组背包，每组有主次之分，不超过，最大价值
1981. 最小化目标值与所选元素的差
分组背包，每组选一个且必选一个，恰好，是否可行