class075 背包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