动态规划：多重背包问题II

背包问题II"/>

动态规划：多重背包问题II

文章目录

• 往期
• 题目
• 解题思路
• • 多重背包的二进制优化
• Reference

往期

1. 01背包问题
2. 完全背包问题
3. 多重背包问题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} log2​k件新的物品， 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} log2​k个新数，可以凑出 0 ∼ k 0 \sim k 0∼k中的任何一个数。这 log ⁡ 2 k \log_{2}{k} log2​k个数作为新物品的系数，新物品的体积和价值就是原物品的费用和价值乘以这个系数。

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

1. 背包问题九讲
2. 多重背包的二进制拆分代码
3. 多重背包问题的优化思路
4. 多重背包问题的优化思路