POJ 1472 Coins （多重背包+滚动数组）
Coins
import java.io.*;import java.util.*;/* * * author : deng_hui_long * Date : 2013-8-31 **/public class Main {int n,m;int dp[]=new int[1000001];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();m=sc.nextInt();if(n==0&&m==0)break;Node node=new Node();Arrays.fill(dp, 0);for(int i=0;i<n;i++){node.a[i]=sc.nextInt();}for(int i=0;i<n;i++){node.c[i]=sc.nextInt();}for(int i=0;i<n;i++){multiplePack(node.a[i],node.a[i],node.c[i]);}int ans=0;for(int i=1;i<=m;i++){if(dp[i]==i)ans++;}System.out.println(ans);}}//多重背包void multiplePack(int cost,int weight,int amount){if(cost*amount>=m)//大于最大价值，按完全背包处理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<=m;i++){dp[i]=Math.max(dp[i],dp[i-cost]+weight);}}//01背包void zeroOnePack(int cost,int weight){for(int i=m;i>=cost;i--){dp[i]=Math.max(dp[i],dp[i-cost]+weight);}}class Node{int a[]=new int[n];int c[]=new int[n];}}
方法二：滚动数组
import java.io.*;import java.util.*;/* * * author : deng_hui_long * Date : 2013-8-31 **/public class Main {int n,m,MAX=100001;boolean dp[]=new boolean[MAX];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();m=sc.nextInt();if(n==0&&m==0)break;Node node=new Node();for(int i=0;i<n;i++){node.a[i]=sc.nextInt();}for(int i=0;i<n;i++){node.c[i]=sc.nextInt();}Arrays.fill(dp,false);dp[0]=true;int ans=0;//滚动数组for(int i=0;i<n;i++){int u[]=new int[MAX];for(int j=node.a[i];j<=m;j++){if(!dp[j]&&dp[j-node.a[i]]&&node.c[i]>u[j-node.a[i]]){dp[j]=true;u[j]=u[j-node.a[i]]+1;ans++;}}}System.out.println(ans);}}class Node{int a[]=new int[n];int c[]=new int[n];}}