cashmachine.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.*;


/**
 * ID:1276
 * DP,背包问题变种
 * @author yhm
 *
 */
public class CashMachine {

	static int NUM = 0;
	static int VALUE = 1;
	
	static int total = 0;
	static int kindNum = 0;
	static int[][] cash = new int[10][2];
	
	static boolean[] c = new boolean[100000+1];
	static short[][] use = new short[100000+1][10];
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			total = cin.nextInt();
			kindNum = cin.nextInt();
			//int[][] cash = new int[kindNum][2];
			for(int i=0;i<kindNum;i++){
				cash[i][NUM] = cin.nextInt();
				cash[i][VALUE] = cin.nextInt();
			}
			
			solve();			
		}

	}

	
	static void solve(){
		//boolean[] c = new boolean[total+1];
		//int[][] use = new int[total+1][kindNum];
		Arrays.fill(c, false);
		for(int i=0;i<100000+1;i++){
			Arrays.fill(use[i], (short)0);
		}
		int max=0;
		
		
		c[0] = true;
		for(int i=1;i<=total;i++){
			for(int j=0;j<kindNum;j++){
				//枚举每种面值
				int value = cash[j][VALUE];
				int left = i-value;
				if(left>=0){
					if(c[left] && use[left][j]+1<=cash[j][NUM]){
						max = i;
						c[i] = true;
						for(int k=0;k<kindNum;k++){
							use[i][k] = use[left][k];
						}
						use[i][j]++;
					}
				}				
			}
		}
		
		System.out.println(max);
		
	}
	
	

	
}