0/1背包算法

装货问题
隔壁老王开着顺丰的标配货车(限载5吨,含5吨,不考虑限高),想要一次性拿走尽可能重的货物,这些货有红木沙发,有钢材等等。

货物编号   货物重量(单位:kg)
1         509
2         838
3         924
4         650
5         604
6         793
7         564
8         651
9         697
10        649
11        747
12        787
13        701
14        605
15        644

背包算法递归定义最优解的方程式:
wechatimg49
大概解释一下:
i 代表第几个货物,j表示当前容量,w(i)表示第i个货物的重量,v(i)表示第i个货物的价值,m(i,j)表示第i个货物,容量为j的最优解
转态转移的时候有两种情况:
1.可以装下一个 j>= w(i),这种情况可以装入这个物品,比较装入后和没有装入的最优解,决定是否装入
2.不可以装下一个 0<=j<=w(i), 这种情况不能装入这个物品,最优解不变

代码实现:


public static int knapsack(int val[], int wt[], int W) {
	int N = wt.length;
	
        //构造一个二维数组
	int[][] V = new int[N + 1][W + 1];
        //初始化数组数据
	for (int col = 0; col <= W; col++) {
		V[0][col] = 0;
	}
         
	for (int row = 0; row <= N; row++) {
		V[row][0] = 0;
	}

	for (int item = 1; item <= N; item++) {
		for (int weight = 1; weight <= W; weight++) {
			if (wt[item - 1] <= weight) {
                //可以装入
				V[item][weight] = Math.max(val[item - 1] + V[item - 1][weight - wt[item - 1]], V[item - 1][weight]);
			} else {
                //不能装入
				V[item][weight] = V[item - 1][weight];
			}
		}

	}

	// 计算选择结果
	int j = W;
	int length = N;
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = length; i > 0; --i) {
		//转态转移的时候记录
		if (V[i][j] > V[i - 1][j]) {
			stringBuilder.append(i).append("-");
			j = j - wt[i-1];
		}
	}
	String result = stringBuilder.toString();
	System.out.println("选择的序号 : " + result.substring(0, result.length()-1));
	
	//打印表
	for (int[] rows : V) {
	      for (int col : rows) {
		System.out.format("%5d", col);
	       }
	      System.out.println();
	}

	return V[N][W];
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注