HDU 1171 Big Event in HDU （多重背包）

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19108    Accepted Submission(s): 6707

Problem DescriptionInputOutputSample InputSample Outputimport java.io.*;import java.util.*;public class Main {int n;int dp[]=new int[100000];int sum,vsum;public static void main(String[] args) {new Main().work();}void work(){Scanner sc=new Scanner(new BufferedInputStream(System.in));while(sc.hasNext()){n=sc.nextInt();if(n<0) break;Node node[]=new Node[n];Arrays.fill(dp, 0);vsum=sum=0;for(int i=0;i<n;i++){int v=sc.nextInt();int m=sc.nextInt();sum+=v*m;node[i]=new Node(v,m);}vsum=sum>>1;// 设备要尽量评分，所以要除以2：注：右一位代表除以2for(int i=0;i<n;i++){multiplyPack(node[i].v,node[i].v,node[i].m);}System.out.println((sum-dp[vsum])+" "+dp[vsum]);}}void multiplyPack(int cost,int weight,int amount){if(cost*amount>=vsum){//如果价值大于总共价值的一半，假设设备是无限的,按照完全背包来处理completePack(cost,weight);}else{//如果小于总共价值的一半，即按照01背包来处理int k=1;while(k<amount){zeroOnePack(k*cost,k*weight);amount-=k;k<<=1;//左一位代表乘以2}zeroOnePack(amount*cost,amount*weight);}}//01背包void zeroOnePack(int cost,int weight){for(int i=vsum;i>=cost;i--){dp[i]=Math.max(dp[i],dp[i-cost]+weight);}}//完全背包void completePack(int cost,int weight){for(int i=cost;i<=vsum;i++){dp[i]=Math.max(dp[i],dp[i-cost]+weight);}}class Node{int v;int m;Node(int v,int m){this.v=v;this.m=m;}}}