精华内容
下载资源
问答
  • 证明贪心算法的结构 第一步:符合贪心选择的特性(Greedy Choice Property) 我们需要证明我们的第一个选择(贪心选择 Greedy Choice,First Choice)包含在某些最优解中 第二步:符合归纳法结构(Inductive ...

     

    部分背包问题

    证明贪心算法的结构

    第一步:符合贪心选择的特性(Greedy Choice Property)

    我们需要证明我们的第一个选择(贪心选择 Greedy Choice,First Choice)包含在某些最优解中

     

    第二步:符合归纳法结构(Inductive Structure)

    我们需要证明第一个选择(贪心选择)\widehat{c}之后,子问题P'和原问题P还是同一类问题,意味着我们的选择不改变问题的结构,并且子问题P'的解可以和第一个选择(贪心选择)\widehat{c}合并

     

    第三步:最优子结构(Optimal Substructure)

    如果我们可以最优的解决子问题P',我们可以将子问题P'的解和贪心选择\widehat{c}得到原问题P的解

    问题本身

    输入:

    • n个物品,每个物品i有自身的重量和价值(w_i, v_i)
    • 1个背包,背包最多可以存放重量为M的物品

    前提:每个物品可以只取其中的一部分,比如拿0.5个某物品i

    输出:

    • 在每个物品可以只取其中的一部分的前提下,使得背包内物品价值最大

    定义我们的算法:

    按照每个物品的密度d_i= \frac{v_i}{w_i}给物品进行升序排列,然后从密度最高的物品开始选,如果空间不够存放一整个物品,就能存放多少部分这个物品就存放多少部分(Best fit)

    证明符合贪心选择的特性:

    Claim:让物品i^*为最高密度的物品,假设这里存在一个最优解用到了w=min(w_i,M)这么多重量的物品i^*

    证明:

    \pi ^*为最优解,

    • 如果\pi ^*用到了w=min(w_i,M)多的物品i^*,那么已经证明了我们的第一个选择(Greedy Choice,First Choice)包含在某些最优解中。
    • 如果\pi ^*没有用到w=min(w_i,M)多的物品i^*,那么我么可以将背包中任意一部分和物品i^*进行交换,因为我们是按照物品密度排序,而且我们已经定义物品i^*为最高密度的物品,所以与物品i^*交换的物品必然比物品i^*的密度要小,所以等量交换后,我们得到的解\pi '会比\pi ^*更优,这个结论与和\pi ^*为最优解的假设冲突,所以最优解\pi ^*中必然含有w=min(w_i,M)多的物品i^*。因此符合贪心选择的特性(Greedy Choice Property)。

    证明符合归纳法结构(Inductive Structure)

    Claim:在完成第一个选择(贪心选择)\widehat{c}之后,子问题P'和原问题P还是同一类问题,意味着我们的选择不改变问题的结构,并且子问题P'的解可以和第一个选择(贪心选择)\widehat{c}合并

    证明:

    • 子问题P'含有除了物品i^*之外的所有物品,背包容量变成了M'=M-w_{i}^*,因此物品i^*可以和子问题P'的解合并。

    证明最优子结构(Optimal Substructure)

    Claim:定义P为原问题,P'为在完成第一个选择(贪心选择)\widehat{c}之后的子问题,\pi '为子问题P'的最优解,那么\pi = \pi ' \cup {\widehat{c}}为原问题P的最优解

    证明:

    • v^*=w\cdot d_i为贪心选择\widehat{c}ww=min(w_i,M)
    • 那么value(\pi )=value(\pi ^{'})+v^*

    假设\pi不是最优解,有一个其他的最优解\pi^*,因为我们已经证明了算法符合贪心选择的特性,所以我们知道最优解\pi^*中一定含有贪心选择\widehat{c}

    • 那么\pi ^*-\widehat{c}就应该是子问题P'的解
    • 所以value(\pi ^*-\widehat{c})=value(\pi ^*)-v^*>value(\pi )-v^*=value(\pi ')
    • 但是这与\pi '为子问题P'的最优解的定义产生冲突,所以\pi = \pi ' \cup {\widehat{c}}不可能不是最优解,因为\pi = \pi ' \cup {\widehat{c}}为原问题P的最优解。QED

     

     

    展开全文
  • 一,部分背包问题贪心算法 部分背包问题可以用贪心算法求解,且能够得到最优解。 贪心策略是什么呢?将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品。 单位重量所具有的价值...

    一,部分背包问题的贪心算法

    部分背包问题可以用贪心算法求解,且能够得到最优解。

    贪心策略是什么呢?将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品。

    单位重量所具有的价值:Vi / Wi

    举个例子:假设背包可容纳50Kg的重量,物品信息如下:

    物品 i      重量(Kg)      价值           单位重量的价值

    1             10          60                 6

    2             20          100               5

    3             30          120               4

    按照我们的贪心策略,单位重量的价值排序: 物品1 > 物品2 > 物品3

    因此,我们尽可能地多拿物品1,直到将物品1拿完之后,才去拿物品2.....

    最终贪心选择的结果是这样的:物品1全部拿完,物品2也全部拿完,物品3拿走10Kg(只拿走了物品3的一部分!!!)

    这种选择获得的价值是最大的。


    二,部分背包问题的贪心策略的正确性证明

    贪心策略是:总是优先选择单位重量下价值最大的物品

    正确性证明 是:使用该贪心策略,可以获得最优解。在这里,最优解就是带走的物品价值最大。

    证明思路:先考察一个全局最优解,然后对该解加以修改(一般是采用“剪枝”技巧),使其采用贪心选择,这个选择将原问题变成一个相似的、但是更小的问题。

    先假设 物品集合S={W1,W2....Wn}已经按 单位重量价值从小到大排好序了。

    并假设 一个全局最优解是:S(i)={Wi1,Wi2,.....Win}。Wi1,Wi2,.....Win是有序的。对于贪心选择而言,总是会优先 选择 Wn 的物品,当Wn 没有后,再选择Wn-1 .....

    如果Win = Wn 问题已经得证。因为,我们的最优解S(i)中,已经包含了贪心选择。只要继续归纳下去,Wi(n-1) 就是 Wn-1 ....

    如果Win != Wn 运用剪枝技巧,剪掉Win 并 贴上 Wn  此时,得到的是一个更优的解(因为价值更大了 ,Wn > Win)。因为,Wn 是单位重量价值最高的那个物品啊,我们的贪心选择应该选择它,但是这里的最优解S(i)却没有选择它,于是我们用剪枝技巧,将它加入到S(i)中去,并把S(i)中的Win除去。  

    这就证明了,如果用贪心策略来进行选择,得到的是最优解。从而证明了贪心算法的正确性。

    其实,也就是证明了一定存在一个最优解,这个最优解就是由贪心选择组成的。


    原文链接

    展开全文
  • 贪心算法通过做出一系列选择来求出问题的最优解。在每个决策点,它做出在当时看来最佳的选择。这种启发式策略并不保证总能找到最优解,但对有些问题确实有效 贪心算法一般步骤 1.确定问题的最优子结构 2.设计一个...

    贪心算法通过做出一系列选择来求出问题的最优解。在每个决策点,它做出在当时看来最佳的选择。这种启发式策略并不保证总能找到最优解,但对有些问题确实有效

    贪心算法一般步骤

    1.确定问题的最优子结构

    2.设计一个递归算法(递归式等)

    3.证明如果我们做出一个贪心选择,则只剩下一个子问题

    4.证明贪心选择总是安全的(步骤3、4的顺序可以调换)

    5.设计一个递归算法实现贪心策略

    6.将递归算法转换为迭代算法

    更一般地,我们可以按如下步骤设计贪心算法:

    • 将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解

    • 证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安全的。

    • 证明做出贪心选择后,剩余的子问题满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

    贪心选择性质和最优子结构是证明一个贪心算法是否能求解一个最优化问题的两个关键要素

    贪心选择性质

    1.做出局部最优(贪心)选择来构造全局最优解,直接做出在当前问题中看来最优的选择,而不必考虑子问题的解

    2.如果进行贪心选择时我们不得不考虑众多选择,通常意味着可以改进贪心选择,使其更为高效

    最优子结构

    如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。此性质是能否应用动态规划和贪心方法的关键要素。

    当应用于贪心算法时,我们通常使用更为直接的最优子结构。如前所述,我们可以假定,通过对原问题应用贪心选择即可得到子问题。我们真正要做的全部工作就是论证:将子问题的最优解与贪心选择组合在一起就能生成原问题的最优解,这种方法隐含地对子问题使用了数学归纳法,证明了在每个步骤进行贪心选择会生成原问题的最优解

    0-1背包问题的贪心与动态规划差别

    0-1背包问题是指:一个正在抢劫商店的小偷发现了n个商品,第i个商品价值vi美元,重wi磅,vi和wi都是整数。这个小偷希望拿走价值尽量高的商品,但他的背包最多能容纳W磅重的商品,W是一个整数。他应该拿哪些商品呢?

    (这个问题是0-1背包问题,因为对每个商品,小偷要么把它完整拿走,要么把它留下。他不能只拿走一个商品的一部分,或者把一个商品拿走多次)

     

    分析:考虑重量不超过W而价值最高的装包方案。

    如果我们将商品j从此方案中删除,则剩余商品必须是重量不超过W-wj的价值最高的方案(小偷只能从不包括商品j的n-1个商品中选择拿走哪些)

    但实际上,贪心策略对0-1背包问题是无效的。考虑包含3个商品和一个能容纳50磅重量的背包。

    • 商品1重10磅,价值60美元

    • 商品2重20磅,价值100美元

    • 商品3重30磅,价值120美元

    商品1的每磅价值为6美元,高于商品2的每磅价值(5美元)和商品3的每磅价值(4美元)。因此,上述贪心策略会首先拿走商品1;

    但是结合0-1背包问题定义,最优解应该拿走商品2和商品3,而留下商品1.拿走商品1的两种方案都是次优的。也就说明这一贪心策略对0-1背包问题无效

    更多算法原理可前往公众号免费获取

    展开全文
  • 为了证明算法的正确性,还必须证明背包问题具有贪心选择性质。这种贪心选择策略对0-1 背包问题就不适用了。看下图例子,其中有3中物品,背包的容量为50千克。物品1重10千克;价值60元;物品2重20千克;价值100元;...

    border="0" width="330" height="86" src="//music.163.com/outchain/player?type=2&id=426343036&auto=0&height=66">

    算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此,算法的计算时间上界为O(nlogn)。为了证明算法的正确性,还必须证明背包问题具有贪心选择性质。这种贪心选择策略对0-1 背包问题就不适用了。看下图例子,其中有3中物品,背包的容量为50千克。物品1重10千克;价值60元;物品2重20千克;价值100元;物品3重30千克,价值120元。因此,物品1每千克价值6元,物品2每千克价值5元,物品3每千克价值4元。若依贪心选择策略,应首先选择物品1装入背包,然而从图b中各种情况可以看出,最优的选择方案是选择物品2和物品3装入背包。首选物品1的两种方案都不是最优的。对于背包问题,贪心选择最终可得到最优解,其选择方案如图c所示。

    对于0-1背包问题,贪心选择之所以不能得到最优解是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。事实上,在考虑0-1背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。

    代码如下:

    #include <stdio.h>    
    #include <iostream>    
    #include<algorithm>  
    using namespace std;  
    #define N 1000  
    struct bag{    
        int w;//物品的重量    
        int v;//物品的价值    
        double c;//物品的性价比     
    }a[1001];     
    bool cmp(bag a,bag b)    
    {    
     return a.c>=b.c;    
    }    
    
    double backpack(int n,bag a[],double c)//n表示物品的数量,a表示按照物品性价比排序后的数组,c表示剩余空间     
    {    
        double cleft=c;  
        int i=0;    
        double b=0;//获得的价值    
        //当物品i可以装入背包中    
        while(i<n&&a[i].w<c)    
        {    
            c=c-a[i].w;    
            b+=a[i].v;    
            i++;        
        }       
        //说明物品不能完全装入背包     
        if(i<n)    
            b+=1.0*a[i].v*c/a[i].w ;    
        return b;    
    }     
    int main()    
    {    
        int c;    
        int n;    
        int i;   
        printf("请输入物品的容量:\n");    
        scanf("%d",&c);  
        printf("请输入每个物品的数量:\n");  
        scanf("%d",&n);    
        printf("请输入每个物品的重量,价值:\n");  
            for(i=0; i<n; i++)    
            {    
                cin>>a[i].w>>a[i].v;    
                a[i].c = 1.0*a[i].v/a[i].w;    
            }    
            sort(a, a+n, cmp);//按照性价比排序   
            printf("输出贪心算法最优解:\n");  
            cout<<backpack(n,a,c);    
        return 0;       
    }     

    运行效果:

    参考博客 0022算法笔记——【贪心算法】背包问题,最优装载问题

    我的个人博客网站

    展开全文
  • 证明贪心算法的正确性 证明贪心算法的结构 第一步:符合贪心选择的特性(Greedy Choice Property) 第二步:符合归纳法结构(Inductive Structure) 第三步:最优子结构(Optimal Substructure) 例子:部分...
  • 之前的课程中,我们学习了运用贪心算法解决问题的两个例子:最少纸币问题和埃及分数问题。在进一步学习用贪心算法解决问题的技巧之前,我们先做一个小结。贪心算法逐步构建问题的解决方案,总是选择能直接带来当前...
  • 第二种:可以且分的物品,物品只有1件(贪心算法) 第三种:物品个数有N种多件 因为可以切分,最后背包会装满 一般大家都能想到的贪心策略: 选择单位价值最优的,所以首先要求解单位价值,然后按照单位价值排序 ...
  • 背包问题贪心算法背包问题 ---- * 已知有n种物品和一个可容纳M重量的背包,每种物品i的重量是w[i]。假定将物品i的一部分x[i]放入背包就会得到p[i]x[i]的效益,这里, * 0[i],p[i]>0.采用怎样的方法才能使装包...
  • 贪心算法贪心算法都可以改写成为动态规划算法 ...贪心算法必须进行证明:数学归纳法 证明: 举例说明: 但是不可以求01背包问题 但是可以求解背包问题: 求单位下的价值 二、最优装载问题 最优装
  • 前面的几篇博文都是围绕动态规划求解最优解问题,但是最优解还有另一种算法就是贪心算法。 动态规划会研究一个问题是否具有最优子结构,然后把问题化为子问题,一般自底向上的求解子问题最终组合出原问题的最优解,...
  • 1.用贪心策略设计与实现一个贪心算法,求解 背包问题 背包问题描述:给定 n 种物品和一个背包,物品 i 的重量是 w[i], 其价值是 p[i], 背包的容量为 C。设物品已按单位重量价值递减的次序排序。每种物品不可以装入...
  • 背包问题贪心选择性质证明

    千次阅读 2018-06-12 11:19:20
    对于背包问题可以用贪心算法求解,作为01背包的上界函数下面证明背包问题满足贪心选择性质:设有一按照单位价值排序好的最优解T=(tk,....tn)第一个装入的物品是tk若k=1则存在贪心性质出发的最优解若k不等于1:如果...
  • 完全背包问题贪心

    千次阅读 2017-03-27 08:50:23
    很容易证明背包问题不能使用贪心算法。然而我们考虑这样一种背包问题:在选择物品i装入背包时,可以选择物品的一部分,而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为...
  • 掌握贪心算法中贪心选择性质的分析与证明; 掌握贪心算法求解问题的方法。 3.实验要求 (1)根据实验内容构思设计算法,选取适合的数据结构;  (2)对所设计的算法采用大O符号进行时间复杂性分析;  (3)上机实现算法...
  • 贪心证明背包问题: 个最优解。 证明基本思想:通过将贪心法的解与任何最优解进行比较来证明。如果这两个解不同,就找出不相等的且下标最小的第一个,从中可推出与假设矛盾的结论。 证明:设X=(x1,…xn)是...
  • 背包问题看贪心,回溯,动态规划 本文很多内容来源于极客时间上 数据结构与算法之美 这一专栏. 本文采用的编程语言是 JavaScript. ...要证明贪心算法的正确性是比较难的.实际情况下要用反证法证明不能用贪心.
  • 预告,突起想起之前证明过一个一级目录二级目录三级目录 我想起当时证明出来特开心,虽然不会长更博弈论,还是可以分享一下(在其它文中有人说没想通)!晚上回家就写,书和证明都在家里。 一级目录 二级目录 三级...
  • 贪心算法

    2019-08-10 09:59:31
    贪心算法概念设计贪心算法的步骤案例剪绳子问题描述解决思路Java代码实现背包问题问题描述解决思路 概念 贪心算法指的是使每个操作看起来都是当前最佳的,期望通过多个局部最优解得到全局最优解。 设计贪心算法的...
  • 前面介绍了JS贪心算法解决背包问题,这里再来看看找零问题的解决方法。 在现实生活中,经常遇到找零问题,假设有数目不限的面值为20,10,5,1的硬币。 给出需要找零数,求出找零方案,要求:使用数目最少的硬币。 对于...
  • 部分背包问题贪心选择性质的证明

    万次阅读 2014-11-01 13:13:01
    最近算法课讲到贪心算法,感觉书本上对bufentanxin
  • 贪心算法理论

    2019-10-05 11:05:41
    贪心算法就是总是做出当前看来最好的选择。即贪心算法并不从整体最优考虑,它做出的选择只是某种意义上的...说明:若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解。 贪...
  • 部分背包(贪心)今天复习贪心,看老师的讲义关于贪心的正确性的证明,直接把我给看傻了,先写个...部分背包问题 贪心策略求解 */ #include #define N 3//背包个数 #define M 20//背包最大承载重量 using namespace
  • 算法_8:贪心算法

    2016-02-29 21:50:49
    贪心算法:局部最优 递归贪心算法迭代贪心算法贪心算法 确定问题的最优子结构 设计递归算法 证明做出贪心选择,则剩下一个子问题 递归算法实现贪心 将递归转换为迭代 0-1背包问题

空空如也

空空如也

1 2 3 4 5
收藏数 86
精华内容 34
关键字:

背包问题证明贪心算法