dividing.java

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

package PKU.DP;
import java.util.Arrays;
import java.util.Scanner;


/**
 * ID:1014
 * DP
 * @author yhm
 *
 */
public class Dividing {

	static int NUM = 0;
	static int VALUE = 1;
	
	static int total = 0;
	static int kindNum = 6;
	static int[][] cash = new int[6][2];
	

	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int sum = 1;
		while(cin.hasNext()){
			total=0;
			for(int i=0;i<6;i++){
				cash[i][VALUE] = i+1;
				cash[i][NUM] = cin.nextInt();
				total += cash[i][VALUE]*cash[i][NUM];
			}
			if(total==0) break;
			
			System.out.println("Collection #"+sum+":");
			if(total%2!=0){
				System.out.println("Can't be divided.");
			}
			else{
				total /= 2;
				solve();
			}
			System.out.println();
			sum++;
			
		}

	}

	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);
//		}

		
		
		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]){
						c[i] = true;
						for(int k=0;k<kindNum;k++){
							use[i][k] = use[left][k];
						}
						use[i][j]++;
					}
				}				
			}
		}
		
		System.out.println(c[total]?"Can be divided.":"Can't be divided.");
		
	}
	
}