class075 背包dp-多重背包、混合背包【算法】-阿里云开发者社区

class075 背包dp-多重背包、混合背包【算法】

算法讲解075【必备】背包dp-多重背包、混合背包

code1 P1776 宝物筛选

// 多重背包不进行枚举优化

// 宝物筛选

// 一共有n种货物, 背包容量为t

// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出

// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值

// 测试链接 : https://www.luogu.com.cn/problem/P1776

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

dp[i][j]：1-i号货物自由选择,每种货物的个数都不超过限制，容量不超过j的情况下获得的最大价值

i号货物：w[i]重量 v[i]价值 c[i]个数

1）dp[i-1][j]

2）dp[i-1][j-w[i]]+v[i]，要1个

3）dp[i-1][j-2w[i]]+2v[i]，要2个

4）…

枚举所有可能的个数，不能超过c[i]

package class075;
// 多重背包不进行枚举优化
// 宝物筛选
// 一共有n种货物, 背包容量为t
// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code01_BoundedKnapsack {
  public static int MAXN = 101;
  public static int MAXW = 40001;
  public static int[] v = new int[MAXN];
  public static int[] w = new int[MAXN];
  public static int[] c = new int[MAXN];
  public static int[] dp = new int[MAXW];
  public static int n, t;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      t = (int) in.nval;
      for (int i = 1; i <= n; i++) {
        in.nextToken(); v[i] = (int) in.nval;
        in.nextToken(); w[i] = (int) in.nval;
        in.nextToken(); c[i] = (int) in.nval;
      }
      out.println(compute2());
    }
    out.flush();
    out.close();
    br.close();
  }
  // 严格位置依赖的动态规划
  // 时间复杂度O(n * t * 每种商品的平均个数)
  public static int compute1() {
    // dp[0][....] = 0，表示没有货物的情况下，背包容量不管是多少，最大价值都是0
    int[][] dp = new int[n + 1][t + 1];
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= t; j++) {
        dp[i][j] = dp[i - 1][j];
        for (int k = 1; k <= c[i] && w[i] * k <= j; k++) {
          dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
        }
      }
    }
    return dp[n][t];
  }
  // 空间压缩
  // 部分测试用例超时
  // 因为没有优化枚举
  // 时间复杂度O(n * t * 每种商品的平均个数)
  public static int compute2() {
    for (int i = 1; i <= n; i++) {
      for (int j = t; j >= 0; j--) {
        for (int k = 1; k <= c[i] && w[i] * k <= j; k++) {
          dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
        }
      }
    }
    return dp[t];
  }
}

code2 P1776 宝物筛选

// 多重背包通过二进制分组转化成01背包(模版)

// 宝物筛选

// 一共有n种货物, 背包容量为t

// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出

// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值

// 测试链接 : https://www.luogu.com.cn/problem/P1776

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

通过二进制分组转化成01背包(模版)

衍生商品1 2 4 8 16 … 的01背包可以组成

原商品多重背包任意一种情况

package class075;
// 多重背包通过二进制分组转化成01背包(模版)
// 宝物筛选
// 一共有n种货物, 背包容量为t
// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Code02_BoundedKnapsackWithBinarySplitting {
  public static int MAXN = 1001;
  public static int MAXW = 40001;
  // 把每一种货物根据个数做二进制分组，去生成衍生商品
  // 衍生出来的每一种商品，价值放入v、重量放入w
  public static int[] v = new int[MAXN];
  public static int[] w = new int[MAXN];
  public static int[] dp = new int[MAXW];
  public static int n, t, m;
  // 时间复杂度O(t * (log(第1种商品的个数) + log(第2种商品的个数) + ... + log(第n种商品的个数)))
  // 对每一种商品的个数取log，所以时间复杂度虽然大于O(n * t)，但也不会大多少
  // 多重背包最常用的方式
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      t = (int) in.nval;
      m = 0;
      for (int i = 1, value, weight, cnt; i <= n; i++) {
        in.nextToken(); value = (int) in.nval;
        in.nextToken(); weight = (int) in.nval;
        in.nextToken(); cnt = (int) in.nval;
        // 整个文件最重要的逻辑 : 二进制分组
        // 一般都使用这种技巧，这段代码非常重要
        // 虽然时间复杂度不如单调队列优化的版本
        // 但是好写，而且即便是比赛，时间复杂度也达标
        // 二进制分组的时间复杂度为O(log cnt)
        for (int k = 1; k <= cnt; k <<= 1) {
          v[++m] = k * value;
          w[m] = k * weight;
          cnt -= k;
        }
        if (cnt > 0) {
          v[++m] = cnt * value;
          w[m] = cnt * weight;
        }
      }
      out.println(compute());
    }
    out.flush();
    out.close();
    br.close();
  }
  // 01背包的空间压缩代码(模版)
  public static int compute() {
    Arrays.fill(dp, 0, t + 1, 0);
    for (int i = 1; i <= m; i++) {
      for (int j = t; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
      }
    }
    return dp[t];
  }
}

code3 P1833 樱花

// 观赏樱花

// 给定一个背包的容量t，一共有n种货物，并且给定每种货物的信息

// 花费(cost)、价值(val)、数量(cnt)

// 如果cnt == 0，代表这种货物可以无限选择

// 如果cnt > 0，那么cnt代表这种货物的数量

// 挑选货物的总容量在不超过t的情况下，返回能得到的最大价值

// 背包容量不超过1000，每一种货物的花费都>0

// 测试链接 : https://www.luogu.com.cn/problem/P1833

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

其中完全背包的货物的个数换成背包容量（最够大）

多重背包转为二进制分组背包

package class075;
// 观赏樱花
// 给定一个背包的容量t，一共有n种货物，并且给定每种货物的信息
// 花费(cost)、价值(val)、数量(cnt)
// 如果cnt == 0，代表这种货物可以无限选择
// 如果cnt > 0，那么cnt代表这种货物的数量
// 挑选货物的总容量在不超过t的情况下，返回能得到的最大价值
// 背包容量不超过1000，每一种货物的花费都>0
// 测试链接 : https://www.luogu.com.cn/problem/P1833
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
// 完全背包转化为多重背包
// 再把多重背包通过二进制分组转化为01背包
public class Code03_CherryBlossomViewing {
  public static int MAXN = 100001;
  public static int MAXW = 1001;
  public static int ENOUGH = 1001;
  public static int[] v = new int[MAXN];
  public static int[] w = new int[MAXN];
  public static int[] dp = new int[MAXW];
  public static int hour1, minute1, hour2, minute2;
  public static int t, n, m;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    in.parseNumbers();
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      hour1 = (int) in.nval;
      // 跳过冒号
      in.nextToken();
      in.nextToken();
      minute1 = (int) in.nval;
      in.nextToken();
      hour2 = (int) in.nval;
      // 跳过冒号
      in.nextToken();
      in.nextToken();
      minute2 = (int) in.nval;
      if (minute1 > minute2) {
        hour2--;
        minute2 += 60;
      }
      // 计算背包容量
      t = (hour2 - hour1) * 60 + minute2 - minute1;
      in.nextToken();
      n = (int) in.nval;
      m = 0;
      for (int i = 0, cost, val, cnt; i < n; i++) {
        in.nextToken();
        cost = (int) in.nval;
        in.nextToken();
        val = (int) in.nval;
        in.nextToken();
        cnt = (int) in.nval;
        if (cnt == 0) {
          cnt = ENOUGH;
        }
        // 二进制分组
        for (int k = 1; k <= cnt; k <<= 1) {
          v[++m] = k * val;
          w[m] = k * cost;
          cnt -= k;
        }
        if (cnt > 0) {
          v[++m] = cnt * val;
          w[m] = cnt * cost;
        }
      }
      out.println(compute());
    }
    out.flush();
    out.close();
    br.close();
  }
  // 01背包的空间压缩代码(模版)
  public static int compute() {
    Arrays.fill(dp, 0, t + 1, 0);
    for (int i = 1; i <= m; i++) {
      for (int j = t; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
      }
    }
    return dp[t];
  }
}

code4 P1776 宝物筛选

// 多重背包单调队列优化

// 宝物筛选

// 一共有n种货物, 背包容量为t

// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出

// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值

// 测试链接 : https://www.luogu.com.cn/problem/P1776

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

需要一个指标

单调队列：从大到小

还要维持淘汰

package class075;
// 多重背包单调队列优化
// 宝物筛选
// 一共有n种货物, 背包容量为t
// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code04_BoundedKnapsackWithMonotonicQueue {
  public static int MAXN = 101;
  public static int MAXW = 40001;
  public static int[] v = new int[MAXN];
  public static int[] w = new int[MAXN];
  public static int[] c = new int[MAXN];
  public static int[] dp = new int[MAXW];
  public static int[] queue = new int[MAXW];
  public static int l, r;
  public static int n, t;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      t = (int) in.nval;
      for (int i = 1; i <= n; i++) {
        in.nextToken();
        v[i] = (int) in.nval;
        in.nextToken();
        w[i] = (int) in.nval;
        in.nextToken();
        c[i] = (int) in.nval;
      }
      out.println(compute2());
    }
    out.flush();
    out.close();
    br.close();
  }
  // 严格位置依赖的动态规划 + 单调队列优化枚举
  public static int compute1() {
    int[][] dp = new int[n + 1][t + 1];
    for (int i = 1; i <= n; i++) {
      for (int mod = 0; mod <= Math.min(t, w[i] - 1); mod++) {
        l = r = 0;
        for (int j = mod; j <= t; j += w[i]) {
          // dp[i-1][j]
          // dp[i][j]
          // queue[r - 1] -> x
          // j -> y
          while (l < r && dp[i - 1][queue[r - 1]] + inc(j - queue[r - 1], i) <= dp[i - 1][j]) {
            // queue[r-1]是队列尾部的列号 vs j这个列号
            // 指标之间pk
            r--;
          }
          queue[r++] = j;
          if (queue[l] == j - w[i] * (c[i] + 1)) {
            // 检查单调队列最左的列号，是否过期
            // 比如
            // i号物品，重量为3，个数4
            // queue[l]是队列头部的列号，假设是2
            // 当j == 17时，依赖的格子为dp[i-1][17、14、11、8、5]
            // 所以此时头部的列号2，过期了，要弹出
            l++;
          }
          // dp[i][j] = dp[i-1][拥有最强指标的列] + (j - 拥有最强指标的列) / i号物品重量 * i号物品价值
          dp[i][j] = dp[i - 1][queue[l]] + inc(j - queue[l], i);
        }
      }
    }
    return dp[n][t];
  }
  // s的容量用来装i号商品，可以得到多少价值
  public static int inc(int s, int i) {
    return s / w[i] * v[i];
  }
  // 单调队列优化枚举 + 空间压缩
  // 理解了原理之后，这个函数就没有理解难度了
  // 难度来自实现和注意边界条件，可以自己尝试一下
  public static int compute2() {
    for (int i = 1; i <= n; i++) {
      for (int mod = 0; mod <= Math.min(t, w[i] - 1); mod++) {
        // 因为空间压缩时，关于j的遍历是从右往左，而不是从左往右
        // 所以先让dp[i-1][...右侧的几个位置]进入窗口
        l = r = 0;
        for (int j = t - mod, k = 0; j >= 0 && k <= c[i]; j -= w[i], k++) {
          while (l < r && dp[j] + inc(queue[r - 1] - j, i) >= dp[queue[r - 1]]) {
            r--;
          }
          queue[r++] = j;
        }
        // 然后j开始从右往左遍历
        // 注意，因为j从右往左遍历，所以：
        // 更靠右的j位置更早进入窗口
        // 更靠左的j位置更晚进入窗口
        for (int j = t - mod; j >= 0; j -= w[i]) {
          // 来到j，计算dp[i][j]的值，做了空间压缩，所以去更新dp[j]
          dp[j] = dp[queue[l]] + inc(j - queue[l], i);
          // 求解完dp[j]
          // 接下来要去求解dp[j-w[i]]了(根据余数分组)
          // 所以看看窗口最左的下标是不是j(其实代表dp[i-1][j]的值]
          // 是的话，说明最左下标过期了，要弹出
          if (queue[l] == j) {
            l++;
          }
          // 最后
          // 因为接下来要去求解dp[j-w[i]]了
          // 所以新的dp[i-1][enter]要进入窗口了
          // 用单调队列的更新方式让其进入
          int enter = j - w[i] * (c[i] + 1);
          if (enter >= 0) {
            while (l < r && dp[enter] + inc(queue[r - 1] - enter, i) >= dp[queue[r - 1]]) {
              r--;
            }
            queue[r++] = enter;
          }
        }
      }
    }
    return dp[t];
  }
}

code5 1742–Coins

// 混合背包 + 多重背包普通窗口优化

// 能成功找零的钱数种类

// 每一种货币都给定面值val[i]，和拥有的数量cnt[i]

// 想知道目前拥有的货币，在钱数为1、2、3…m时

// 能找零成功的钱数有多少

// 也就是说当钱数的范围是1~m

// 返回这个范围上有多少可以找零成功的钱数

// 比如只有3元的货币，数量是5张

// m = 10

// 那么在1~10范围上，只有钱数是3、6、9时，可以成功找零

// 所以返回3表示有3种钱数可以找零成功

// 测试链接 : http://poj.org/problem?id=1742

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

bool dp[i][j]：1…i号货币能否找零j元

①i:1个 01背包

dp[i-1][j]||dp[i-1][j-值i]

②i:面值乘以个数超过m：完全背包

dp[i-1][j]||dp[i][j-值i]

③其余：多重背包

统计窗口中的True的个数，>0就是True

不需要单调队列，不需要设立指标

package class075;
// 混合背包 + 多重背包普通窗口优化
// 能成功找零的钱数种类
// 每一种货币都给定面值val[i]，和拥有的数量cnt[i]
// 想知道目前拥有的货币，在钱数为1、2、3...m时
// 能找零成功的钱数有多少
// 也就是说当钱数的范围是1~m
// 返回这个范围上有多少可以找零成功的钱数
// 比如只有3元的货币，数量是5张
// m = 10
// 那么在1~10范围上，只有钱数是3、6、9时，可以成功找零
// 所以返回3表示有3种钱数可以找零成功
// 测试链接 : http://poj.org/problem?id=1742
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Code05_MixedKnapsack {
  public static int MAXN = 101;
  public static int MAXM = 100001;
  public static int[] val = new int[MAXN];
  public static int[] cnt = new int[MAXN];
  public static boolean[] dp = new boolean[MAXM];
  public static int n, m;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      m = (int) in.nval;
      if (n != 0 || m != 0) {
        for (int i = 1; i <= n; i++) {
          in.nextToken();
          val[i] = (int) in.nval;
        }
        for (int i = 1; i <= n; i++) {
          in.nextToken();
          cnt[i] = (int) in.nval;
        }
        out.println(compute());
      }
    }
    out.flush();
    out.close();
    br.close();
  }
  // 直接提供空间压缩版
  public static int compute() {
    Arrays.fill(dp, 1, m + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
      if (cnt[i] == 1) {
        // 01背包的空间压缩实现是从右往左更新的
        for (int j = m; j >= val[i]; j--) {
          if (dp[j - val[i]]) {
            dp[j] = true;
          }
        }
      } else if (val[i] * cnt[i] > m) {
        // 完全背包的空间压缩实现是从左往右更新的
        for (int j = val[i]; j <= m; j++) {
          if (dp[j - val[i]]) {
            dp[j] = true;
          }
        }
      } else {
        // 多重背包的空间压缩实现
        // 根据余数分组
        // 每一组都是从右往左更新的
        for (int mod = 0; mod < val[i]; mod++) {
          int trueCnt = 0;
          for (int j = m - mod, size = 0; j >= 0 && size <= cnt[i]; j -= val[i], size++) {
            trueCnt += dp[j] ? 1 : 0;
          }
          for (int j = m - mod, l = j - val[i] * (cnt[i] + 1); j >= 1; j -= val[i], l -= val[i]) {
            if (dp[j]) {
              trueCnt--;
            } else {
              if (trueCnt != 0) {
                dp[j] = true;
              }
            }
            if (l >= 0) {
              trueCnt += dp[l] ? 1 : 0;
            }
          }
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) {
      if (dp[i]) {
        ans++;
      }
    }
    return ans;
  }
}

2023-11-20 17:20:26

class075 背包dp-多重背包、混合背包【算法】