0-1背包问题与分数背包问题

  • 0⑴背包问题与分数背包问题
    • 问题描写
    • 问题分析之分数背包
    • 代码设计之分数背包问题
    • 问题分析之0⑴背包问题
    • 代码设计之0⑴背包问题
    • 动态计划算法之间的差别

0⑴背包问题与分数背包问题

我们在文章《贪心算法原理》:http://blog.csdn.net/ii1245712564/article/details/45369491中提到过动态计划和贪心算法的区分。和两个经典的例子:0⑴背包问题分数背包问题,我么知道0⑴背包问题是不能够使用贪心算法求解的,而贪心算法则是分数背包问题的不2之选。
这次我们来侧重实现1下0⑴背包问题的动态计划解法和分数背包问题的贪心算法。

问题描写

  • 0⑴背包问题:我们有1堆物品S={a1,a2,...,an},每个物品ai都有1个重量wi和1个价值vi.现在有1个背包,这个背包的容量为W,现在要将这些物品在不超越背包容量的情况下选择性的放入背包,使得背包里面物品的价值最大,物品不能只选取其中1部份,必须选择全部,或不选!

  • 分数背包问题:这个问题和上面的问题比较类似,唯1不同的就是该问题里面的物品可以进行分割,便可以只选取1个物品ai的1部份

这里我们采取例子:

我们有3个物品和1个容量为50的背包,这3个物品<重量,价值>分别为:a1<10,60>,a2<20,100>,a3<30,120>.

问题分析之分数背包

为简单期间,我们首先来分析1下分数背包问题。如果要设计1个贪心算法,那末首先要肯定1个贪心策略,换句话说就是要怎样在当前的情况下做出1个公道的贪心选择。
我们首先得到每个物品单位重量的价值vi/wi,那末我们要设计1个贪心策略来使得装入背包物品的价值最大。我们的第1直觉肯定是要选择单位重量价格最高的喽,然后再选择物品里面第2高的,1次类推直到装满背包为止!

下面我们来证明1下上面贪心选择的料想:

证明:

我们首先假定我们有1个最优解A1,那末我们首先找到A1里面平均价值最高的物品am,让后我们将用商品里面平均价值最高的物品a1am进行全部替换或部份替换得到解A2,又因v1/w1vm/wm所以A2的总价值高于A1的总价值,这A1是最优解矛盾,因而得到A1里面包括平均价值最高的物品。

因而我们得到最优子结构Si=Sk+akakSi里面平均价值最高的,Sk是选择ak剩下来的物品。

代码设计之分数背包问题

依照我们上面描写的分数背包问题的最好贪心策略,每次都选出平均价值最高的物品

/*************************************************
* @Filename: fractionPackage.cc
* @Author: qeesung
* @Email: qeesung@qq.com
* @DateTime: 2015-04⑶0 14:44:28
* @Version: 1.0
* @Description: 贪心策略,分数背包问题
**************************************************/

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

#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的1部份进入到背包。这里也很好理解,那就是我们在物品总能装满背包的情况下,背包总是可以被装满的,我们如果要使总价值最高,那我们就应当提升平均的价值密度,那就把平均价值最高的顺次放入背包!

问题分析之0⑴背包问题

为何我们不能用贪心算法来解决0⑴背包问题呢,我们只需要举1个反例就能够了,我们还是依照之前的将平均价值最大的放入背包里面,放入a1,然后a2,a3已不能再放入了,因而我们得到背包物品总价值为60+100=160,但是这个是最优解么?肯定不是,由于只放入a2a3总价值就到达100+120=220,所以这里我们只能另辟蹊径。
每个物品只有两种选择,那就是放入背包与不放入背包。所以我们要做的就是决定1个物品是放入还是不放入背包。
在求解动态计划问题中,我们首先要做的,就是找到最优子结构递归表达式。因而我们假定f(i,W)为有<

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 0-1背包问题与分数背包问题

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡