数据结构与算法学习之路：背包问题的贪心算法和动态规划算法

一、背包问题描述：

有N种物品和一个重量为M的背包，第i种物品的重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量，且价值总和最大。

二、解决方法：

1、贪心算法：贪心算法基于的思想是每一次选择都作当前最好的选择，这样最后的结果虽然不一定是最优解，但是也不会比最优解差很多。

举个例子说明可能好懂一些：一帮基友去聚餐，菜是一份一份上的，我每一次夹菜都只夹牛肉/海鲜吃，可能到最后我吃的牛肉/海鲜很多，但不一定代表我吃掉的东西的总价值最高，但是相对来说价值也很高了～

换句话说，对于贪心算法，其核心在于设定一个标准让我们去贪。回到这个问题，这个标准就有三种设法了：1、价值最高的先装进背包；2、重量最低的先装进包；3、性价比（价值和重量的比值）最高的先装进背包。我在这里用的是第三种方法，用快排作了排序。

在装的过程中要注意的就是，当前物品能不能放进背包。这个是需要考虑的。因为背包问题也有好几种，如：0-1背包问题（每种物品只能拿一次）、完全背包问题（每种物品都能拿无限次）、多重背包问题（每种物品都有一定的数量可以拿）。所以在不同情况下贪心算法的一些细节设计也是不一样的，这个需要自己考虑。

2、动态规划算法：贯穿动态规划算法的就是状态和状态转移方程这两个东西，而要得到这两个东西需要我们把我们的问题分解为更小的子问题，通过分析子问题去获得。这个我在LIS问题上也讲过（数据结构与算法学习之路：LIS——最长递增序列的动态规划算法和二分思想算法）

那么回到我们这个问题，由于每次装东西进背包，我们只考虑能否装进，以及是否当前状态下的最优选择，也就是说，我们需要用背包的容量去设计一个数组，存储每一单位个容量的最大价值是多少，以此类推，获得背包容量下的最大价值是多少。这样说可能说不清楚，看看下面的代码吧～

三、代码：

1、贪心算法：

void Greedy_KnapSack(Greedy_BagPtr greedy_bags, float bagWeight){
	float temp = bagWeight;

	Quick_Sort(greedy_bags, 0, 9);

	for (int i = 9; i >= 0; --i){
		if (greedy_bags[i].weight <= temp){
			temp -= greedy_bags[i].weight;
			greedy_bags[i].resultWeight = 1;
		}
		else if (greedy_bags[i].weight > temp && temp > 0){
			greedy_bags[i].resultWeight = temp / greedy_bags[i].weight;
			temp = 0;
		}
		else if (temp < 0)
			return;
	}
}

2、动态规划算法：

int DP_KnapSack(DP_BagPtr dp_bags, int bagWeight){
	int i, size = bagWeight + 1,currentMaxValue;

	int *dp_bagweight = (int*)malloc(size*sizeof(int));

	dp_bagweight[0] = 0;

	for (i = 1; i < size; ++i){
		currentMaxValue = 0;

		if (i <= 9 && i > 0){
			for (int j = 0; j < BAGSIZE; ++j){
				if (dp_bags[j].weight == i && dp_bags[j].value > currentMaxValue)
					currentMaxValue = dp_bags[j].value;
			}

			if ((dp_bagweight[i - 1] + 1) > currentMaxValue)
				dp_bagweight[i] = dp_bagweight[i - 1] + 1;
			else
				dp_bagweight[i] = currentMaxValue;
		}
		else{
			if ((dp_bagweight[i - 1] + 1) > (dp_bagweight[9] + dp_bagweight[i % 9]))
				dp_bagweight[i] = dp_bagweight[i - 1] + 1;
			else
				dp_bagweight[i] = dp_bagweight[9] + dp_bagweight[i % 9];
		}
	}
	return dp_bagweight[bagWeight];
}

void Quick_Sort(Greedy_BagPtr bags, int start, int end){
	if (start < end){
		int i = start, j = end;
		Greedy_Bag temp = bags[start];

		while (i < j){
			while (i < j && bags[j].relativeValue >= temp.relativeValue)
				--j;
			if (i < j)
				bags[i++] = bags[j];
			while (i < j && bags[i].relativeValue < temp.relativeValue)
				++i;
			if (i < j)
				bags[j--] = bags[i];
		}
		bags[i].value = temp.value;
		bags[i].weight = temp.weight;
		bags[i].resultWeight = temp.resultWeight;
		bags[i].relativeValue = temp.relativeValue;
		Quick_Sort(bags, start, i - 1);
		Quick_Sort(bags, i + 1, end);
	}
}