Java教程

0-1背包问题 Java

本文主要是介绍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);
		}
		
}

这篇关于0-1背包问题 Java的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!