动态规划法求背包装物品价值最大的问题

问题描述：

假定背包的最大容量为W（千克），有N件物品，每件物品都有自己的价值和重量，将哪些物品放入背包中可使得背包内物品的总价值最大。

假设:

W = 10; N = 4;

物品重量数组：weights[4] = {5, 4, 6, 3};

物品价值数组：values[4]   = {10, 40, 30, 50} 

可参考网址：http://www.importnew.com/13072.html 

 

解决这个问题可以使用动态规划法，即先解决部分，再利用已解决的内容，解决后面的问题。

具体方法是设置了一个二维表，行代表物品数量，从0个物品到N个物品一共N+1行，列代表背包剩余可容纳重量同理有W+1列。每一个元素都是代表背包剩余重量为w时，有n个物品时，背包可容纳的最大物品价值。

第0(i-1=0)行代表0个物品的时候，显然背包没物品可装，最大价值均为0；

第0列(w=0)代表背包剩余重量为0时，显然，最大价值也都为0.

第1（i-1 = 1）行第一列开始，代表有一个物品时，背包剩余重量从1到W时，背包可容纳最大物品价值，显然从W>=weights[i-1]开始，最大价值都未物品1的价值。

第2行第一列开始，代表有物品1，2时，背包剩余重量从1到W时，背包可容纳最大物品价值。那么，此时如果背包剩余重量>=物品2重量时，是否应该将物品2放入背包呢，这里就是重点了。

两种方案。

方案一：如果把物品2装进去，这时背包剩余重量 = W - weights[i - 1]，去查一下第一行，的剩余重量处，背包可容纳最大物品价值，将这个价值 + 物品2价值，就是背包将物品2装入以后的价值。

方案二：不装物品2，那么去查询一下背包剩余重量W时，第一行的那个最大价值。

比较方案一，方案二的两个价值，哪个大，取哪个。

理解一下：就是说我装了物品2，物品2的价值加上剩余的空间的最大价值（之前计算出来了的）是不是比不装物品2时背包剩余空间的最大价值（也是上一行已经计算出来的）大，大的话，就装进去，否则就不装，最大价值还取剩余重量W时第一行的值。

 

算法描述完了，可能不太好理解，建议看看那个网址里面的图文。

如果还无法理解，看看下面的C代码吧，这段C代码我在电脑上编译并运行过的，是正确的代码。C代码看了以后，反复阅读方案一、方案二这两行，相信你会懂的。

结果的二维表先贴出来，看着二维表，或许更好理解。

 

0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	10	10	10	10	10	10
0	0	0	0	40	40	40	40	40	50	50
0	0	0	0	40	40	40	40	40	50	70
0	0	0	50	50	50	50	90	90	90	90

add objects: [4][2]

weight:7

 

比如最后一行最后一列数据90举例，这一行最后一个数据的判断：物品4重量为3，背包剩余重量W为10，如果把物品4装入背包，那么背包剩余重量W - 3 = 10 - 3 = 7，查询一下上一行中W = 7，即第0~10列中的第7列（注意从0开始数），最大价值为40 + 物品4的价值50 = 90；

如果不把物品4，放入背包，剩余重量W = 10，查询上一行，W = 10，即最后一列，第10列的最大价值为70。

90 > 70，所以物品4应该放入背包。

这里所有计算都是基于上一行已经计算出的最大价值。

背包可容纳物品最大价值就等于表中所有数据中的最大值。

那么哪些物品被放入背包了呢，从最后一个数据开始看，即90，假设这个值的位置是values[i][w]，那么当values[i-1][w] != values[i][w]时，物品i-1，即物品4肯定是被放入背包了。因为如果物品4不应该放入背包的话，那么上一行的值和这个值应该相等（因为包不包含物品4，都不应该影响背包可容纳最大价值）。这里满足了，上一行是70，所以物品4放入背包。背包剩余重量 = 10 - 3 = 7。

再看剩余重量为7，上一行数据，即40，它是否满足values[i-1][w] != values[i][w]，它不满足，所以物品3没放入。此时W = 7不变。

继续看剩余重量为7的上一行数据，即10，不等于40，所以物品2放入背包。剩余重量7 - 4 = 3.

再看上一行W = 3时，为0，这一行是否等于再上一行呢，相等，所以物品1也没有放入背包，到这里，判断就结束了。这就是代码showWhichAdd实现的功能。

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int **getMaxWeightValuesTable(int *weights, int *values, int num, int maxWeight) {
	int **maxValues = (int **)malloc((num+1) * sizeof(int*));
	memset(maxValues, 0, (num+1) * sizeof(int*));
	int i,weight;
	for (i=0; i<=num; i++) {
		maxValues[i] = (int*)malloc((maxWeight+1) * sizeof(int));
		memset(maxValues[i], 0, (maxWeight+1) * sizeof(int));
	}
	for (i=1; i<=num; i++) {
		for (weight=1; weight<=maxWeight; weight++) {
			if (weight >= weights[i-1]) { // 背包剩余载重还能装这个物品
				if (values[i-1] + maxValues[i-1][weight-weights[i-1]] > maxValues[i-1][weight]) {
					maxValues[i][weight] = values[i-1] + maxValues[i-1][weight-weights[i-1]];
				} else {
					maxValues[i][weight] = maxValues[i-1][weight];
				}
			} else {
				maxValues[i][weight] = maxValues[i-1][weight];
			}
		}
	}
	return maxValues;
}

void showWhichAdd(int **maxValues, int *weights, int num, int maxWeight) {
	int i;
	int weight = maxWeight;
	printf("add objects: ");
	for (i=num; i>=1; i--) {
		if (maxValues[i][weight] != maxValues[i-1][weight]) {
			printf("[%d]", i);
			weight -= weights[i-1];
		}
	}
	printf("\nweight:%d\n", maxWeight - weight);
}

int main(int argc, char **argv) {
	int weights[] = {5, 4, 6, 3};
	int values[] = {10, 40, 30, 50};
	int num = 4;
	int maxWeight = 10;
	int **maxValues = getMaxWeightValuesTable(weights, values, num, maxWeight);
	int i, weight;
	for (i=0; i <= num; i++) {
		for (weight=0; weight <= maxWeight; weight++) {
			printf("%d\t", maxValues[i][weight]);
		}
		printf("\n");
	}
	showWhichAdd(maxValues, weights, num, maxWeight);
	for(i=0; i<=num; i++) {
		free(maxValues[i]);
	}
	free(maxValues);
	maxValues = NULL;

	return 0;
}