部分背包问题

证明贪心算法的结构

第一步：符合贪心选择的特性（Greedy Choice Property）


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


 

第二步：符合归纳法结构（Inductive Structure）


我们需要证明第一个选择（贪心选择）之后，子问题和原问题还是同一类问题，意味着我们的选择不改变问题的结构，并且子问题的解可以和第一个选择（贪心选择）合并


 

第三步：最优子结构（Optimal Substructure）


如果我们可以最优的解决子问题，我们可以将子问题的解和贪心选择得到原问题的解


问题本身


输入：

个物品，每个物品有自身的重量和价值
	
1个背包，背包最多可以存放重量为的物品
前提：每个物品可以只取其中的一部分，比如拿0.5个某物品

输出：

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


定义我们的算法：


按照每个物品的密度给物品进行升序排列，然后从密度最高的物品开始选，如果空间不够存放一整个物品，就能存放多少部分这个物品就存放多少部分（Best fit）




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


Claim：让物品为最高密度的物品，假设这里存在一个最优解用到了这么多重量的物品


证明：

让为最优解，

如果用到了多的物品，那么已经证明了我们的第一个选择（Greedy Choice，First Choice）包含在某些最优解中。
	
如果没有用到多的物品，那么我么可以将背包中任意一部分和物品进行交换，因为我们是按照物品密度排序，而且我们已经定义物品为最高密度的物品，所以与物品交换的物品必然比物品的密度要小，所以等量交换后，我们得到的解会比更优，这个结论与和为最优解的假设冲突，所以最优解中必然含有多的物品。因此符合贪心选择的特性（Greedy Choice Property）。
证明符合归纳法结构（Inductive Structure）


Claim：在完成第一个选择（贪心选择）之后，子问题和原问题还是同一类问题，意味着我们的选择不改变问题的结构，并且子问题的解可以和第一个选择（贪心选择）合并


证明：

子问题含有除了物品之外的所有物品，背包容量变成了，因此物品可以和子问题的解合并。
证明最优子结构（Optimal Substructure）


Claim：定义为原问题，为在完成第一个选择（贪心选择）之后的子问题，为子问题的最优解，那么为原问题的最优解


证明：

让为贪心选择（是）
	
那么
假设不是最优解，有一个其他的最优解，因为我们已经证明了算法符合贪心选择的特性，所以我们知道最优解中一定含有贪心选择

那么就应该是子问题的解
	
所以
	
但是这与为子问题的最优解的定义产生冲突，所以不可能不是最优解，因为为原问题的最优解。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.设计一个递归算法（递归式等）

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背包问题无效

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

 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算法笔记——【贪心算法】背包问题,最优装载问题

我的个人博客网站