一、背包问题描述：

有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];

}

3、可能有人会需要，在解决这个问题的情况下我修改的快排

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);

}

}