第七天二进制优化多重背包java代码

背包java代码"/>

第七天二进制优化多重背包java代码

我们试想一哈，将多重背包的物品件数以一为单位拆成N份，对于每一份，我们都考虑选与不选，这就是多重背包转01背包的思想。但是这样的拆法对于本题来说会直接超时。这就要要到二进制的思想，比如一件物品8件，就可以按照二进制展开成1,2，4,1（因为1+2+4>8，所以1=8-1-2-4）四份，这样通过1,2，4,1四份的其中每一份的选与 不选都可以表示出8以内的数字，而且是四份，不是8份，大大缩小了遍历次数；

import java.util.*;
public class Main{public static void main(String[] args){Scanner in=new Scanner(System.in);int m=in.nextInt();//物品种类int n=in.nextInt();//背包总大小int a[]=new int[n+1];//背包大小为n时候，a[n]的最优解int ans=0;for(int i=1;i<=m;i++){int w=in.nextInt();//重量int v=in.nextInt();//价值int c=in.nextInt();//限制LinkedList<num> number=new LinkedList<num>(); //重复新建，内容肯定会重置for(int j=1;j<=c;j*=2){//1,2,4,8.......c-=j;number.add(new num(j*w,j*v));//二进制优化（多重背包转01背包），即提取份数}if(c>0){//看最后一个数的拆分，保证所有份数加起来可以凑到这个物品的总数number.add(new num(c*w,c*v));}for(int k=0;k<number.size();k++){for(int y=n;y>=((num)number.get(k)).w;y--){a[y]=Math.max(a[y],a[y-((num)number.get(k)).w]+((num)number.get(k)).v);//当前最优ans=Math.max(ans, a[y]);//最终取最优}}}System.out.println(ans);}
}
class num{int w,v;num(int w,int v){this.w=w;this.v=v;}
}