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

发布时间：2020-12-13 20:47:25 所属栏目：PHP教程来源：网络整理

导读：0⑴背包问题与分数背包问题问题描写问题分析之分数背包代码设计之分数背包问题问题分析之0⑴背包问题代码设计之0⑴背包问题动态计划算法之间的差别 0⑴背包问题与分数背包问题我们在文章《贪心算法原理》:http://blog.csdn.net/ii1245712564/article/

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

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

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

问题描写

0⑴背包问题：我们有1堆物品 $S=lbrace a_1,a_2,...,a_n brace$ ,每个物品 $a_i$ 都有1个重量 $w_i$ 和1个价值 $v_i$ .现在有1个背包，这个背包的容量为 $W$ ,现在要将这些物品在不超越背包容量的情况下选择性的放入背包，使得背包里面物品的价值最大，物品不能只选取其中1部份，必须选择全部，或不选！

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

这里我们采取例子：

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

问题分析之分数背包

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

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

证明:

我们首先假定我们有1个最优解 $A_1$ ,那末我们首先找到 $A_1$ 里面平均价值最高的物品 $a_m$ ，让后我们将用商品里面平均价值最高的物品 $a_1$ 将 $a_m$ 进行全部替换或部份替换得到解 $A_2$ ，又因 $v_1/w_1 geq v_m/w_m$ 所以 $A_2$ 的总价值高于 $A_1$ 的总价值，这 $A_1$ 是最优解矛盾，因而得到 $A_1$ 里面包括平均价值最高的物品。

因而我们得到最优子结构 $S_i = S_k +a_k$ ， $a_k$ 是 $S_i$ 里面平均价值最高的， $S_k$ 是选择 $a_k$ 剩下来的物品。

代码设计之分数背包问题

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

/*************************************************
* @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个反例就能够了，我们还是依照之前的将平均价值最大的放入背包里面，放入 $a_1$ ,然后 $a_2$ , $a_3$ 已不能再放入了，因而我们得到背包物品总价值为 $60+100=160$ ，但是这个是最优解么？肯定不是,由于只放入 $a_2$ 和 $a_3$ 总价值就到达 $100+120=220$ ,所以这里我们只能另辟蹊径。
每个物品只有两种选择，那就是放入背包与不放入背包。所以我们要做的就是决定1个物品是放入还是不放入背包。
在求解动态计划问题中，我们首先要做的,就是找到最优子结构和递归表达式。因而我们假定 $f(i,W)$ 为有<

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!