背包问题_13.pdf

问题描述

有 N 种物品和一个容量是 V 的背包。
物品一共有三类：

  • 第一类物品只能用1次（01背包）；
  • 第二类物品可以用无限次（完全背包）；
  • 第三类物品最多只能用 si 次（多重背包）；

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

  • si=−1 表示第 i 种物品只能用1次；
  • si=0 表示第 i 种物品可以用无限次；
  • si>0 表示第 i 种物品可以使用 si 次；

输出格式
输出一个整数，表示最大价值。
数据范围
00−1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8

思路：
将01，完全，多重背包组合起来即可。

二维版本

  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();
  12.         for (int i = 1; i <= n; i++) {
  13.             int v = sc.nextInt(), w = sc.nextInt(), s = sc.nextInt();
  14.             if (s == 0) {
  15.                 for (int j = 0; j <= m; j++) {
  16.                     f[i][j] = f[i - 1][j];
  17.                     if (j >= v)
  18.                         f[i][j] = Math.max(f[i][j], f[i][j - v] + w);
  19.                 }
  20.             } else {
  21.                 if (s == -1) s = 1;
  22.                 // 不选
  23.                 for (int j = 0; j <= m; j++)
  24.                     f[i][j] = f[i - 1][j];
  25.                 // 选
  26.                 for (int k = 1; k <= s; k <<= 1) {
  27.                     for (int j = m; j >= k * v; j--) {
  28.                         f[i][j] = Math.max(f[i][j], f[i][j - k * v] + w * k);
  29.                     }
  30.                     s -= k;
  31.                 }
  32.                 if (s > 0) {
  33.                     for (int j = m; j >= s * v; j--) {
  34.                         f[i][j] = Math.max(f[i][j], f[i][j - s * v] + w * s);
  35.                     }
  36.                 }
  37.             }
  38.         }
  39.         System.out.println(f[n][m]);
  40.     }
  41. }

一维版本

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