多重背包Ⅰ

背包问题_4.pdf

问题描述

Acwing 4. 多重背包问题I
多重背包，每件物品数量有效，不超过，最大价值
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
00输入样例

  1. 4 5
  2. 1 2 3
  3. 2 4 1
  4. 3 4 3
  5. 4 5 2

输出样例：

  1. 10

二维版

与最裸的完全背包基本一致！多了物品数的判断

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 110, M = 110;
  5.     static int[][] f = new int[N][M];
  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();
  12.         // 遍历物品
  13.         for (int i = 1; i <= n; i++) {
  14.             int v = sc.nextInt(), w = sc.nextInt(), c = sc.nextInt();
  15.             // 遍历体积
  16.             for (int j = 0; j <= m; j++) {
  17.                 // 遍历决策
  18.                 for (int k = 0; k <= c && k * v <= j; k++) {
  19.                     f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v] + k * w);
  20.                 }
  21.             }
  22.         }
  23.         System.out.println(f[n][m]);
  24.     }
  25. }

一维版

与不去掉枚举物品数的一维版本完全背包基本一致！

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 110, M = 110;
  5.     static int[] f = new int[M];
  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();
  12.         for (int i = 1; i <= n; i++) {
  13.             int v = sc.nextInt(), w = sc.nextInt(), c = sc.nextInt();
  14.             for (int j = m; j >= v; j--) {
  15.                 for (int k = 0; k <= c && k * v <= j; k++)
  16.                     f[j] = Math.max(f[j], f[j - k * v] + k * w);
  17.             }
  18.         }
  19.         System.out.println(f[m]);
  20.     }
  21. }

多重背包 Ⅱ

背包问题_5.pdf

问题描述

Acwing 5. 多重背包问题 II
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
000

提示：

本题考查多重背包的二进制优化方法。
输入样例

  1. 4 5
  2. 1 2 3
  3. 2 4 1
  4. 3 4 3
  5. 4 5 2

输出样例：

  1. 10

时间复杂度：O(NVlogS)

二维版

  1. import java.util.*;
  3. public class Main {
  4.     static int N = 1010, M = 2010;
  5.     static int[][] f = new int[N][M];
  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();
  12.         for (int i = 1; i <= n; i++) {
  13.             int v = sc.nextInt(), w = sc.nextInt(), s = sc.nextInt();
  15.             for (int j = 0; j <= m; j++)
  16.                 f[i][j] = f[i - 1][j];
  17.             for (int k = 1; k <= s; k <<= 1) {
  18.                 for (int j = m; j >= k * v; j--) {
  19.                     f[i][j] = Math.max(f[i][j], f[i][j - k * v] + k * w);
  20.                 }
  21.                 s -= k;
  22.             }
  23.             if (s > 0) {
  24.                 for (int j = m; j >= s * v; j--) {
  25.                     f[i][j] = Math.max(f[i][j], f[i][j - s * v] + s * w);
  26.                 }
  27.             }
  28.         }
  29.         System.out.println(f[n][m]);
  30.     }
  31. }

一维版

直接去掉物品维即可

  1. import java.util.*;
  3. public class Main {
  4.     static int N = 1010, M = 2010;
  5.     static int[] f = new int[M];
  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();
  12.         for (int i = 1; i <= n; i++) {
  13.             int v = sc.nextInt(), w = sc.nextInt(), s = sc.nextInt();
  15.             for (int k = 1; k <= s; k <<= 1) {
  16.                 for (int j = m; j >= k * v; j--)
  17.                     f[j] = Math.max(f[j], f[j - k * v] + k * w);
  18.                 s -= k;
  19.             }
  21.             if (s > 0) {
  22.                 for (int j = m; j >= s * v; j--) 
  23.                     f[j] = Math.max(f[j], f[j - s * v] + s * w);
  24.             }
  25.         }
  26.         System.out.println(f[m]);
  27.     }
  28. }
  1. // 另一种写法
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 1010, M = 2010;
  6.     static int[] V = new int[30], W = new int[30];
  7.     static int n, m;
  8.     static int[] f = new int[M];
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  12.         n = sc.nextInt();
  13.         m = sc.nextInt();
  15.         for (int i = 1; i <= n; i++) {
  16.             int v = sc.nextInt(), w = sc.nextInt(), c = sc.nextInt();
  17.             int idx = 1, p = 1;
  18.             while (c >= p) {
  19.                 c -= p;
  20.                 V[idx] = v * p;
  21.                 W[idx] = w * p;
  22.                 idx++;
  23.                 p <<= 1;
  24.             }
  25.             if (c > 0) {
  26.                 V[idx] = v * c;
  27.                 W[idx] = w * c;
  28.                 idx++;
  29.             }
  30.             for (int k = 0; k < idx; k++)
  31.                 for (int j = m; j >= V[k]; j--)
  32.                     f[j] = Math.max(f[j], f[j - V[k]] + W[k]);
  33.         }
  34.         System.out.println(f[m]);
  35.     }
  36. }

多重背包 Ⅲ

背包问题_6.pdf

问题描述

6. 多重背包问题 III
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
000

提示

本题考查多重背包的单调队列优化方法。
输入样例

  1. 4 5
  2. 1 2 3
  3. 2 4 1
  4. 3 4 3
  5. 4 5 2

输出样例：

  1. 10

二维版

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

滚动数组优化

  2. // 滚动数组版本
  3. import java.util.*;
  5. public class Main {
  6.     static final int N = 1010, M = 20010;
  7.     static int[][] f = new int[2][M];
  8.     static int n, m;
  9.     static int[] q = new int[M];
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         n = sc.nextInt();
  13.         m = sc.nextInt();
  14.         int hh, tt;
  16.         for (int i = 1; i <= n; i++) {
  17.             int v = sc.nextInt(), w = sc.nextInt(), s = sc.nextInt();
  18.             for (int k = 0; k < v; k++) {
  19.                 hh = 0; tt = -1;
  20.                 for (int j = k; j <= m; j += v) {
  21.                     if (hh <= tt && q[hh] < j - s * v)
  22.                         hh++;
  23.                     while (hh <= tt && f[i-1&1][q[tt]] - (q[tt] - k) / v * w <= f[i-1&1][j] - (j - k) / v * w)
  24.                         tt--;
  25.                     q[++tt] = j;
  26.                     f[i&1][j] = f[i-1&1][q[hh]] + (j - q[hh]) / v * w;
  27.                 }
  28.             }
  29.         }
  30.         System.out.println(f[n&1][m]);
  31.     }
  32. }
  33. // 数组复制版本
  34. import java.util.*;
  36. public class Main {
  37.     static final int N = 1010, M = 20010;
  38.     static int[] f = new int[M], g = new int[M];
  39.     static int n, m;
  40.     static int[] q = new int[M];
  41.     public static void main(String[] args) {
  42.         Scanner sc = new Scanner(System.in);
  43.         n = sc.nextInt();
  44.         m = sc.nextInt();
  45.         int hh, tt;
  47.         for (int i = 1; i <= n; i++) {
  48.             int v = sc.nextInt(), w = sc.nextInt(), s = sc.nextInt();
  49.             System.arraycopy(f, 0, g, 0, m + 1);
  50.             for (int k = 0; k < v; k++) {
  51.                 hh = 0; tt = -1;
  52.                 for (int j = k; j <= m; j += v) {
  53.                     if (hh <= tt && q[hh] < j - s * v)
  54.                         hh++;
  55.                     while (hh <= tt && g[q[tt]] - (q[tt] - k) / v * w <= g[j] - (j - k) / v * w)
  56.                         tt--;
  57.                     q[++tt] = j;
  58.                     f[j] = g[q[hh]] + (j - q[hh]) / v * w;
  59.                 }
  60.             }
  61.         }
  62.         System.out.println(f[m]);
  63.     }
  64. }
  1. // 20220407 更新
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 1010, M = 20010;
  6.     static int[][] f = new int[N][M];
  7.     static int n, m;
  8.     static int[] q = new int[M];
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  12.         n = sc.nextInt();
  13.         m = sc.nextInt();
  15.         for (int i = 1; i <= n; i++) {
  16.             int v = sc.nextInt(), w = sc.nextInt(), s = sc.nextInt();
  17.             for (int k = 0; k < v; k++) {
  18.                 int hh = 0, tt = -1;
  19.                 for (int j = k; j <= m; j += v) {
  20.                     if (hh <= tt && q[hh] < j - s * v)
  21.                         hh++;
  22.                     // 这里的判断做了一点修改，本质一样，但更好写了。
  23.                     while (hh <= tt && f[i-1][j] >= f[i-1][q[tt]] + (j-q[tt]) / v * w)
  24.                         tt--;
  25.                     q[++tt] = j;
  26.                     f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v * w;
  27.                 }
  28.             }
  29.         }
  30.         System.out.println(f[n][m]);
  31.     }
  32. }

基础
Acwing 154. 滑动窗口
其它例题
AcWing 1019. 庆功会
多重背包，不超过，最大价值

多重背包求方案数

AcWing 451. 摆花
多重背包，恰好，方案数

多重背包Ⅰ

  1. // 最暴力的写法
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 110, M = 110, MOD = 1000007;
  6.     static int[][] f = new int[N][M];
  7.     static int n, m;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         m = sc.nextInt();
  14.         f[0][0] = 1;
  15.         for (int i = 1; i <= n; i++) {
  16.             int s = sc.nextInt();
  17.             for (int j = 0; j <= m; j++) {
  18.                 for (int k = 0; k <= s && k <= j; k++)
  19.                     f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD; 
  20.             }
  21.         }
  22.         System.out.println(f[n][m]);
  23.     }
  24. }
  1. // 优化掉物品维
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 110, M = 110, MOD = 1000007;
  6.     static int[] f = new int[M];
  7.     static int n, m;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         m = sc.nextInt();
  14.         f[0] = 1;
  15.         for (int i = 1; i <= n; i++) {
  16.             int s = sc.nextInt();
  17.             for (int j = m; j >= 1; j--) {
  18.                 for (int k = 1; k <= s && k <= j; k++)
  19.                     f[j] = (f[j] + f[j - k]) % MOD; 
  20.             }
  21.         }
  22.         System.out.println(f[m]);
  23.     }
  24. }

多重背包Ⅱ

无法求解
例如一个物品个数为2，正常结果为f[1][1] = 1，但是使用二进制优化的结果是f[1][1] = 2

多重背包Ⅲ

不需要单调队列，用一个前缀和(滑动窗口)即可。

  1. // 二维版本
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 110, M = 110, MOD = 1000007;
  6.     static int[][] f = new int[N][M];
  8.     static int n, m;
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         n = sc.nextInt();
  13.         m = sc.nextInt();
  15.         f[0][0] = 1;
  16.         for (int i = 1; i <= n; i++) {
  17.             int s = sc.nextInt();
  18.             int cnt = 0;
  19.             for (int j = 0; j <= m; j++) {
  20.                 cnt = (cnt + f[i - 1][j]) % MOD;
  21.                 f[i][j] = cnt;
  22.                 if (j >= s)
  23.                     cnt = (cnt - f[i - 1][j - s] + MOD) % MOD;
  24.             }
  25.         }
  26.         System.out.println(f[n][m]);
  27.     }
  28. }
  1. // 一维版本
  2. import java.util.*;
  4. public class Main {
  5.     static final int N = 110, M = 110, MOD = 1000007;
  6.     static int[] f = new int[M], g = new int[M];
  8.     static int n, m;
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         n = sc.nextInt();
  13.         m = sc.nextInt();
  15.         f[0] = 1;
  16.         for (int i = 1; i <= n; i++) {
  17.             int s = sc.nextInt();
  18.             System.arraycopy(f, 0, g, 0, m + 1);
  19.             int cnt = 0;
  20.             for (int j = 0; j <= m; j++) {
  21.                 cnt = (cnt + g[j]) % MOD;
  22.                 f[j] = cnt;
  23.                 if (j >= s)
  24.                     cnt = (cnt - g[j - s] + MOD) % MOD;
  25.             }
  26.         }
  27.         System.out.println(f[m]);
  28.     }
  29. }

LCP 25. 古董键盘
多重背包，每组可选[0, k]件物品，恰好选n件，排列数
相较于摆花那道题，没有规定具体排列方式