0-1背包问题 Java

package beiBao;

public class Knapsack {
	//c是背包容量，n是物品的个数，x[]是否装入：0不装入，1装入；w[]物品重量，v[]物品体积，m(i,j)代表背包容量为j时，选择物品从i，i+1，...n,时的最优解。	
		public static void KnapSack(int c,int n, int x[],int w[],int v[],int m[][]) {
			for(int i = 0;i <= n;i++)
				m[i][0] = 0;//背包容量为0
			for(int j = 0;j <=c ;j++)
				m[0][j] = 0;//物品数量为0
			for(int i = 1;i<=n;i++) {
				for(int j = 1;j<=c;j++) {
					if(w[i] > j)//物品i的重量大于背包总重量j，直接舍弃不装它
						m[i][j] = m[i-1][j];
					else
						m[i][j] = Math.max(m[i-1][j], v[i] + m[i-1][j-w[i]]);//i的重量不大于j，也可以选择不装，也可以选择装
				}
			}
			//下面是输出语句
			System.out.println("表f的值");//打印换行
			for(int i = 0;i <= n;i++) {
				for(int j = 0;j<=c;j++)
					System.out.printf("%-4d",m[i][j]);//遍历输出
				System.out.println();//换行，做成表格
			}
			int j = c;//背包容量等于c
			for(int i = n;i > 0;i--) {//物品从n开始遍历，选择要还是不要
			if(m[i][j] > m[i-1][j] ){
				x[i] = 1;
				j -= w[i];//每要一个物品，背包的总重量就要相应的减去这个物品的重量
			}
			else
				x[i] = 0;//这个是不要物品
			}
			System.out.println("表x的值：");
			for(int i = 1;i<=n;i++)
				System.out.println("x" + i + "=" + x[i] +"t");//这里输出要了哪个物品，没要哪个物品
			System.out.println();
			System.out.printf("总价值为：%d",m[n][c]);//总价值怎么出来的呢？这个  m[i][j] = Math.max(m[i-1][j], v[i] + m[i-1][j-w[i]]);
		}
		public static void main(String[] args) {
			int c = 10;
			int n = 5;
			int x[] = new int[n + 1];
			int w[] = new int [] {0,2,2,6,5,4};
			int v[] = new int [] {0,6,3,5,4,6};
			int m[][] = new int[n+1][c+1];
			KnapSack(c, n, x, w, v, m);
		}
		
}