[数据结构与算法]0-1背包问题 Java

0-1背包问题 Java

package beiBao;
/*0-1背包问题：给定n种物品和一个背包。物品i的重量是wi，其价值是vi，背包的容量为c。
 * 问：哪些物品装入背包可使价值总和最大？最大是多少？
 * m(n,j)代表背包容量为j时，选择物品n时候的最优值
 * m(i,j)代表背包容量为j时，选择物品从i，i+1，...n,时的最优解。
 * 思路：
 * 价值：如果物品j的重量大于背包i重量，那么就舍弃，然后m[i][j] = m[i-1][j];
 * 	如果不大于呢，这个也有两个选择，可以装可以不装，条件是：Math.max(m[i-1][j], v[i] + m[i-1][j-w[i]])，装了和不装里面选最大的
 * 装还是不装记录：装：x[i] = 1;不装：x[i] = 0;判定条件：m[i][j] > m[i-1][j] 就把i装进去，反之不装。
 *  
 */
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);
		}
		
}