POJ 1276 ?? Cash Machine（多重背包）
Cash Machineimport java.io.*;import java.util.*;/* * * author : deng_hui_long * Date : 2013-8-31 **/public class Main {int Case,n;int dp[]=new int[1000000];public static void main(String[] args) {new Main().work();}void work(){Scanner sc=new Scanner(new BufferedInputStream(System.in));while(sc.hasNext()){Case=sc.nextInt();n=sc.nextInt();if(n==0&&Case==0)break;Node node[]=new Node[n];Arrays.fill(dp,0);for(int i=0;i<n;i++){int a=sc.nextInt();int b=sc.nextInt();node[i]=new Node(a,b);}for(int i=0;i<n;i++){multiplePack(node[i].val,node[i].val,node[i].cost);}System.out.println(dp[Case]);}}//多重背包void multiplePack(int cost,int weight,int amount){if(cost*amount>=Case)//超过最大的钱数，按完全背包处理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);}}//完全背包void completePack(int cost,int weight){for(int i=cost;i<=Case;i++){dp[i]=Math.max(dp[i],dp[i-cost]+weight);}}//01背包void zeroOnePack(int cost,int weight){for(int i=Case;i>=cost;i--)dp[i]=Math.max(dp[i],dp[i-cost]+weight);}class Node{int cost;int val;Node(int cost,int val){this.cost=cost;this.val=val;}}}