0-1背包问题与分数背包问题
我们在文章《贪心算法原理》:中提到过动态规划和贪心算法的区别。以及两个经典的例子：0-1背包问题和分数背包问题，我么知道0-1背包问题是不能够使用贪心算法求解的，而贪心算法则是分数背包问题的不二之选。 这次我们来着重实现一下0-1背包问题的动态规划解法以及分数背包问题的贪心算法。
问题描述
0-1背包问题：我们有一堆物品,现在要将这些物品在不超出背包容量的情况下选择性的放入背包，使得背包里面物品的价值最大，物品不能只选取其中一部分，必须选择整个，或者不选！
分数背包问题：这个问题和上面的问题比较相似，唯一不同的就是该问题里面的物品可以进行分割，即可以只选取一个物品的一部分
这里我们采用例子：
我们有三个物品和一个容量为.
问题分析之分数背包
为简单期间，我们首先来分析一下分数背包问题。如果要设计一个贪心算法，那么首先要确定一个贪心策略，换句话说就是要怎么在当前的情况下做出一个合理的贪心选择。 我们首先得到每一个物品单位重量的价值,那么我们要设计一个贪心策略来使得装入背包物品的价值最大。我们的第一直觉肯定是要选择单位重量价格最高的喽，然后再选择物品里面第二高的，一次类推直到装满背包为止！
下面我们来证明一下上面贪心选择的猜想：
证明:
我们首先假设我们有一个最优解里面包含平均价值最高的物品。
于是我们得到最优子结构剩下来的物品。
代码设计之分数背包问题
依照我们上面描述的分数背包问题的最佳贪心策略，每次都选出平均价值最高的物品
/************************************************** @Filename: fractionPackage.cc* @Author:qeesung* @Email:qeesung@qq.com* @DateTime: 2015-04-30 14:44:28* @Version:1.0* @Description: 贪心策略，，分数背包问题**************************************************/;#define PACKAGE_CAPACITY 50/** * 求得goodslist对应的最大价值,我们首先假设物品按照平均价值降序排序 * @param goodsList 商品列表 * @return最大价值 */unsigned fractionPackage(std::vector<pair<unsigned , unsigned> > goodsList){unsigned valueSum=0;unsigned capacitySum=0;for (int i = 0; i < goodsList.size(); ++i){// 转完这次就退出if(goodsList[i].second + capacitySum >= PACKAGE_CAPACITY){valueSum+=(PACKAGE_CAPACITY – capacitySum)*(goodsList[i].first/goodsList[i].second);return valueSum;}valueSum+=goodsList[i].first;capacitySum+=goodsList[i].second;}return valueSum;}int main(int argc, char const *argv[]){std::vector<pair<unsigned , unsigned> > goodsList;goodsList.push_back(pair<unsigned , unsigned>(60,10));goodsList.push_back(pair<unsigned , unsigned>(100,20));goodsList.push_back(pair<unsigned , unsigned>(120,30));cout<<“max value is : “<<fractionPackage(goodsList)<<endl;while(1);return 0;}
运行结果为:
max value is 240
我们这里首先选择平均价值最高的a1放入背包，然后放入a2,因为此时a3不能全部放入背包，于是我们放入a3的一部分进入到背包。这里也很好理解，那就是我们在物品总能装满背包的情况下，背包总是可以被装满的，我们如果要使总价值最高，那我们就应该提升平均的价值密度，那就把平均价值最高的依次放入背包！
问题分析之0-1背包问题
为什么我们不能用贪心算法来解决0-1背包问题呢，我们只需要举一个反例就可以了，我们还是按照之前的将平均价值最大的放入背包里面，放入,所以这里我们只能另辟蹊径。 每一个物品只有两种选择，那就是放入背包与不放入背包。所以我们要做的就是决定一个物品是放入还是不放入背包。 在求解动态规划问题中，我们首先要做的,就是找到最优子结构和递归表达式。于是我们假设为有个商品，背包容量为这个物品到底要不要放入到背包里面，决定这个标准是什么?
如果，我们选择值最大的那个！ 如果 痛苦留给的一切，请细加回味!苦难一经过去，苦难就变为甘美。
