AcWing 5. 多重背包问题 II-java
原题链接
中等
作者:
单箭头
,
2019-05-11 16:50:28
,
所有人可见
,
阅读 1647
java 代码
package com.company.ForTruth.ali.背包问题;
import java.util.ArrayList;
import java.util.Scanner;
/**
* Author: hszzjs
* Date: 2019/5/10 19:15
* E-mail: hushaozhe@stu.xidian.edu.cn
* 这个是对于多重背包问题使用二进制优化的方法,依旧是最终转换为01背包。只不过这里不是一件一件拆分,
* 而是s=1+2+4+...+2^k+c,就是通过二进制优化进行转换。
*/
public class 多重背包II {
static class VW{
int v,w;
public VW(int v,int w){
this.v=v;
this.w=w;
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt(),V=sc.nextInt();
ArrayList<VW> vw=new ArrayList<>();
for(int i=0;i<N;i++){
int v=sc.nextInt(),w=sc.nextInt(),s=sc.nextInt();
int tmp=0;
while (s>=Math.pow(2,tmp)){
vw.add(new VW((int) Math.pow(2,tmp)*v,(int)Math.pow(2,tmp)*w));
s-=Math.pow(2,tmp);
tmp+=1;
}
if(s>0) vw.add(new VW(v*s,w*s));
}
int[][] res=new int[vw.size()+1][V+1];
for(int i=1;i<=vw.size();i++){
for(int j=V;j>0;j--){
if(vw.get(i-1).v>j) res[i][j]=res[i-1][j];
else res[i][j]=Math.max(res[i-1][j],res[i-1][j-vw.get(i-1).v]+vw.get(i-1).w);
}
}
System.out.println(res[vw.size()][V]);
}
}