背包问题_9.pdf

AcWing 8. 二维费用的背包问题

二维费用，01背包，不超过，不超过，最大价值
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0000输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8

思路：无非就是在体积的基础上再加一维表示重量

二维版本

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

一维版本

  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, e;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         n = sc.nextInt();
  11.         m = sc.nextInt();
  12.         e = sc.nextInt();
  14.         for (int i = 1; i <= n; i++) {
  15.             int v1 = sc.nextInt(), v2 = sc.nextInt(), w = sc.nextInt();
  16.             for (int j = m; j >= v1; j--) {
  17.                 for (int k = e; k >= v2; k--)
  18.                     f[j][k] = Math.max(f[j][k], f[j - v1][k - v2] + w);
  19.             }
  20.         }
  21.         System.out.println(f[m][e]);
  22.     }
  23. }

Acwing 1022. 宠物小精灵之收服

二维费用，01背包，不超过，不超过，最大价值
思路：与01背包的结合
既要考虑精灵球数量，还得考虑体力
考虑抓到相同数量的宠物时，不管精灵球的剩余数目如何，但得确保剩余体力的最大化
状态表示：f[i][j][k]表示考虑前i个精灵，在总精灵球数不超过j，总体力不超过k的情况下的所有捕捉方式
状态属性：成功捕获的数目
状态计算：根据第i个精灵抓或不抓，分为两类
f[i][j][k] = Math.max(f[i - 1][j][k], f[i - 1][j - c][k - v] + 1
条件是j >= c && k >= v

二维版本

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  7.         // 球数 体力 精灵数
  8.         int m = sc.nextInt(), e = sc.nextInt(), n = sc.nextInt();
  9.         int[][][] f = new int[n + 1][m + 1][e + 1];
  11.         for (int i = 1; i <= n; i++) {
  12.             int c = sc.nextInt(), v = sc.nextInt();
  13.             for (int j = 0; j <= m; j++) {
  14.                 for (int k = 0; k <= e; k++) {
  15.                     f[i][j][k] = f[i - 1][j][k];
  16.                     if (j >= c && k > v)
  17.                         f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j - c][k - v] + 1);
  18.                 }
  19.             }
  20.         }
  21.         int res = e;
  22.         while (res > 0 && f[n][m][res] == f[n][m][e])
  23.             res--;
  24.         System.out.println(f[n][m][e] + " " + (e - res));
  25.     }
  26. }

一维版本

  1. // 去掉物品维度
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 1010, M = 510, K = 110;
  6.     static int[][] f = new int[N][M];
  7.     static int m, e, n;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         m = sc.nextInt();
  11.         e = sc.nextInt();
  12.         n = sc.nextInt();
  14.         for (int i = 1; i <= n; i++) {
  15.             int c = sc.nextInt(), v = sc.nextInt();
  16.             for (int j = m; j >= c; j--) {
  17.                 for (int k = e; k > v; k--) {
  18.                     f[j][k] = Math.max(f[j][k], f[j - c][k - v] + 1);
  19.                 }
  20.             }
  21.         }
  23.         int res = e;
  24.         while (res > 0 && f[m][res] == f[m][e])
  25.             res--;
  26.         System.out.println(f[m][e] + " " + (e - res));
  27.     }
  28. }

其它例题

879. 盈利计划

二维费用，01背包，恰好，不低于，方案数
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

示例 1：
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3] 输出：2 解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。 总的来说，有两种计划。
示例 2：
输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] 输出：7 解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。 有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

  • 1 <= n <= 100
  • 0 <= minProfit <= 100
  • 1 <= group.length <= 100
  • 1 <= group[i] <= 100
  • profit.length == group.length
  • 0 <= profit[i] <= 100

思路：
状态表示：f[i][j][k]表示从前i个工作中选，由j个人去完成且总利润不少于k的所有方案的集和
属性：方案数
初始化：f[0][0][0] = 1表示什么任务也不选，投入0人，总利润为0的方案数为1种
转移：略

  1. class Solution {
  2.     int MOD = (int)(1e9 + 7);
  3.     public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
  4.         int m = group.length;
  5.         int[][][] f = new int[m + 1][n + 1][minProfit + 1];
  7.         f[0][0][0] = 1;
  9.         for (int i = 1; i <= m; i++) {
  10.             int v = group[i - 1], w = profit[i - 1];
  11.             for (int j = 0; j <= n; j++) {
  12.                 for (int k = 0; k <= minProfit; k++) {
  13.                     f[i][j][k] = f[i - 1][j][k];
  14.                     if (j >= v) {
  15.                         f[i][j][k] += f[i - 1][j - v][Math.max(0, k - w)];
  16.                         f[i][j][k] %= MOD;
  17.                     }
  18.                 }
  19.             }
  20.         }
  21.         int res = 0;
  22.         for (int i = 0; i <= n; i++)
  23.             res = (res + f[m][i][minProfit]) % MOD;
  24.         return res;
  25.     }
  26. }
  1. // 去掉物品维
  3. class Solution {
  4.     int MOD = (int)(1e9 + 7);
  5.     public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
  6.         int m = minProfit;
  7.         int[][] f = new int[n + 1][m + 1];
  8.         // 初始化
  9.         f[0][0] = 1;
  11.         // DP
  12.         for (int i = 0; i < group.length; i++) {
  13.             for (int j = n; j >= group[i]; j--) {
  14.                 for (int k = m; k >= 0; k--) {
  15.                     int pre = Math.max(0, k - profit[i]);
  16.                     f[j][k] += f[j - group[i]][pre];
  17.                     f[j][k] %= MOD;
  18.                 }
  19.             }
  20.         }
  22.         int res = 0;
  23.         for (int i = 0; i <= n; i++) {
  24.             res += f[i][m];
  25.             res %= MOD;
  26.         }
  28.         return res;
  29.     }
  30. }
  1. // 换个状态表示
  2. // f[j][k] 表示由不超过j个人完成任务，且总利润不低于k的所有方案
  3. // 属性：方案数
  5. class Solution {
  6.     int MOD = (int)(1e9 + 7);
  7.     public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
  8.         int m = minProfit;
  10.         int[][] f = new int[n + 1][m + 1];
  11.         // 初始化
  12.         for (int i = 0; i <= n; i++) {
  13.             f[i][0] = 1;
  14.         }
  15.         // DP
  16.         for (int i = 0; i < group.length; i++) {
  17.             for (int j = n; j >= group[i]; j--) {
  18.                 for (int k = m; k >= 0; k--) {
  19.                     int pre = Math.max(0, k - profit[i]);
  20.                     f[j][k] += f[j - group[i]][pre];
  21.                     f[j][k] %= MOD;
  22.                 }
  23.             }
  24.         }
  26.         return f[n][m];
  27.     }
  28. }

AcWing 1020. 潜水员

二维费用，01背包，不低于，不低于，最小代价

  1. import java.util.*;
  3. public class Main {
  4.     static final int M = 25, N = 85;
  5.     static int[][] f = new int[M][N];
  6.     static int n, m, size;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         m = sc.nextInt();
  13.         size = sc.nextInt();
  15.         for (int i = 0; i <= n; i++)
  16.             Arrays.fill(f[i], 0x3f3f3f3f);
  18.         f[0][0] = 0;
  19.         while (size-- > 0) {
  20.             int v1 = sc.nextInt(), v2 = sc.nextInt(), w = sc.nextInt();
  21.             for (int i = n; i >= 0; i--) {
  22.                 for (int j = m; j >= 0; j--) {
  23.                     int p1 = Math.max(0, i - v1), p2 = Math.max(0, j - v2);
  24.                     if (f[p1][p2] != 0x3f3f3f3f)
  25.                         f[i][j] = Math.min(f[i][j], f[p1][p2] + w);
  26.                 }
  27.             }
  28.         }
  30.         System.out.println(f[n][m]);
  31.     }
  32. }
474. 一和零 二维费用，01背包，不超过，不超过，最大价值
805. 数组的均值分割 二维费用，01背包，恰好，恰好，是否可行