01背包

package com.bag01;


public class Bag01 {
	public void solution(int []weight,int []price,int n,int count){
		/*
		 * 创建一个数组,其中行便是物品，
		 * 列表示背包可装下物品的剩余容量
		 */
		int [][] max = new int [50][500];
		/*
		 * 对第一件物品可能出现的背包容量进行枚举,
		 * 若是满足容量大于第一件物品的质量，
		 * 那么价值为第一件物品的价值
		 * */
		for(int j=0;j<=count;j++){  //初始化，边界
			if(j<weight[n]){
				max[n][j]=0;
			}else{
				max[n][j]=price[n];
			}
		}
		/*
		 * 递推：
		 * 如果剩余容量大于底i件物品的质量并且加入的第i+1件物品的价值比不装入的价值高。
		 * */
		for(int i=n-1 ; i >= 0;i--){
			for(int j = 0;j<=count;j++){
				if(j>=weight[i] && max[i+1][j]<max[i+1][j-weight[i]]+price[i]){
					max[i][j] = max[i+1][j-weight[i]] +price[i] ;
				}else{ 
					max[i][j] = max[i+1][j];
				}
			}
			
		}
		int countw = count;
		int sprice = 0,sweight=0;
		int o=0;
		//打印
		for(int i= 0;i<=n-1;i++){
			if(max[i][countw]>max[i+1][countw]){ //是否放入
				countw-=weight[i];sweight += weight[i];sprice+=price[i];
				System.out.println("weight:"+weight[i]+"\t price:"+price[i]);
			}
			o++;
		}
		if(max[0][count]-sprice == price[n]){
			sweight+=weight[o];sprice+= price[o];
			System.out.println("weight:"+weight[n]+"\t price:"+price[n]);
		}
	}
	public static void main(String[] args) {
		int[] weight = new int[]{1,2,3,4,5,6};
		int[] price  = new int[]{6,5,4,3,2,1};
		Bag01 bag01 = new Bag01();
		bag01.solution(weight, price,5, 200);
	}
}