背包问题II"/>
动态规划:多重背包问题II
文章目录
- 往期
- 题目
- 解题思路
- 多重背包的二进制优化
- Reference
往期
- 01背包问题
- 完全背包问题
- 多重背包问题I
题目
多重背包问题II
有 N N N 种物品和一个容量是 V V V 的背包。
第 i i i 种物品最多有 s i s_{i} si 件,每件体积是 v i v_{i} vi,价值是 w i w_{i} wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数, N N N, V V V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N N N 行,每行三个整数 v i v_{i} vi, w i w_{i} wi, s i s_{i} si,用空格隔开,分别表示第 i i i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N ≤ 1000 0< N\le 1000 0<N≤1000
0 < V ≤ 2000 0< V\le 2000 0<V≤2000
0 < v i , w i , s i ≤ 2000 0< v_{i},w_{i},s_{i}\le 2000 0<vi,wi,si≤2000
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例
10
解题思路
相比多重背包问题I,本题数据范围变大,需优化时间复杂度。
不能用完全背包问题中抛弃k循环的思路来优化这个问题,因为每个物品的件数不同,不能像完全背包问题那样优化状态转移方程。
多重背包的二进制优化
考虑将多重背包问题转化为01背包问题,考虑把第 i i i种物品换成若干件物品,使得原问题中第 i i i种物品可取的每种策略(取 0 0 0件、取 1 1 1件、…、取 k k k件),均能等价于取若干件转换以后的物品,取超过 k k k件的策略必不能出现。
若直接把第 i i i件物品换成 s [ i ] s[i] s[i]件01背包中的物品,时间复杂度不变。
考虑二进制的思想,将 k k k件物品拆成 log 2 k \log_{2}{k} log2k件新的物品, k = 1 + 2 + 2 2 + . . . + 2 t + c ( c ≤ 2 t + 1 ) k=1+2+2^{2}+...+2^{t}+c\left ( c\le 2^{t+1} \right ) k=1+2+22+...+2t+c(c≤2t+1),用这 log 2 k \log_{2}{k} log2k个新数,可以凑出 0 ∼ k 0 \sim k 0∼k中的任何一个数。这 log 2 k \log_{2}{k} log2k个数作为新物品的系数,新物品的体积和价值就是原物品的费用和价值乘以这个系数。
eg: 13 = 1 + 2 + 4 + 6 13=1+2+4+6 13=1+2+4+6,最多取13件的物品被分成系数分别为 1 , 2 , 4 , 6 1,2,4,6 1,2,4,6的四件物品,原先要枚举14次,拆分之后只需枚举5次;这种优化对于大数尤其明显,例如最多取1024件的物品,在正常情况下要枚举1025次 , 二进制思想下转化成01背包只需要枚举11次。
import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 物品种数int m = sc.nextInt(); // 背包容积int[] v = new int[n];int[] w = new int[n];int[] s = new int[n];for (int i = 0; i < n; i++) {v[i] = sc.nextInt();w[i] = sc.nextInt();s[i] = sc.nextInt();}// 二进制拆分int[] newV = new int[n*11]; // 2^11 = 2048,也就是说s最多可以拆成11个,故数组容量乘以11int[] newW = new int[n*11];int newN = 0; // 新的物品种数for (int i = 0; i < n; i++) {for (int j = 1; j <= s[i]; j *= 2) {newV[newN] = j * v[i]; // 体积newW[newN] = j * w[i]; // 价值s[i] -= j;newN++;}if (s[i] > 0) {newV[newN] = s[i] * v[i];newW[newN] = s[i] * w[i];newN++;}}// 01背包问题int[] dp = new int[m+1]; for (int i = 0; i < newN; i++) {for (int j = m; j >= newV[i]; j--) {dp[j] = Math.max(dp[j], dp[j-newV[i]]+newW[i]);}}System.out.println(dp[m]);}
}
Reference
- 背包问题九讲
- 多重背包的二进制拆分代码
- 多重背包问题的优化思路
- 多重背包问题的优化思路
更多推荐
动态规划:多重背包问题II
发布评论