AcWing 5. 多重背包问题 II Java
个人理解
关于自己学习完这道题的一些个人理解,如果哪里不对还希望大佬多多指正,谢谢。
- 首先也是选择的问题,我们不妨这样考虑N种物品,一种物品S个,假设我们要准备箱子装物品,那么一种物品我们就要准备S个,N种就要准备NS个箱子,然后我们做01背包的判断,即对应每个箱子,我们会考虑选还是不选的问题,那么我们要考虑NS次,会超时。
- 我们依然准备箱子,但是我们没必要准备那么多箱子,我们准备cnt个箱子,当我们拿到一种物品,它有S个,我们会把它拆分成log以2为底的S个(向上取整),比如一种物品有5个,那么我们不会准备5个箱子,而是log2 5 = 3个箱子,每个箱子中的存放的次数k都是2的次幂,从1开始(k = 1),5前两个箱子就是1 2,这里1 + 2 + 4 < 5,所以我们还需要补一个箱子,这个箱子数量就是剩余的s数量。
- 接上,一个物品三个箱子,每个箱子都会有与之对应这个箱子的价值和体积(a * k b * k),类推,我们会有log级别的箱子
- 对应每个箱子我们同01背包的事就可以了,即选还是不选的问题就可以了。这样就变成log级别了
图片理解
题解
import java.io.*;
import java.util.*;
public class Main{
//物品数量最多就是12000 = log2为底2000 *1000 ;M 是背包容量
static int N = 12000,M = 2010,n,m;
static int[] f = new int[M],v = new int[N],w = new int[N];
static int Int(String s){return Integer.parseInt(s);}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args)throws IOException{
String[] arrStr =br.readLine().split(" ");
n = Int(arrStr[0]); m =Int(arrStr[1]);
//准备箱子
int cnt = 0;
for(int i = 1 ;i<= n;i++){
arrStr =br.readLine().split(" ");
//每次箱子的默认都是2的0次方 = 1
int k = 1;
//当前物品的体积,价值,数量
int a =Int(arrStr[0]);int b = Int(arrStr[1]);int s = Int(arrStr[2]);
//二进制拆分数量
while(s >= k){
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k; k*= 2;
}
//需要多加一个箱子来补剩余没有被二进制表示的c
if(s > 0){
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
//一共的箱子数目
n = cnt;
//遍历所有的箱子做0,1背包问题
for(int i = 1; i<= n;i++){
for(int j = m ;j >= v[i]; j--){
f[j] = Math.max(f[j] , f[j- v[i]] + w[i]);
}
}
//输出m容量的最大价值
pw.println(f[m]);
pw.flush();br.close();pw.close();
}
}