贪心算法 背包问题

时间:2021-07-15 04:23:14

部分转自:http://blog.csdn.net/liufeng_king/article/details/8711928


背包问题

     (1)0-1背包问题:给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
     注:在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。

      0-1背包问题可用动态规划算法来求解,具体过程可参看笔者博文《动态规划 金矿模型 01背包问题》。

     (2)背包问题:与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤n。
     2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤是,首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。

     具体代码如下:

[cpp] view plain copy

    //4d2 贪心算法 背包问题  
    #include "stdafx.h"  
    #include <iostream>   
    using namespace std;   
      
    const int N = 3;  
      
    void Knapsack(int n,float M,float v[],float w[],float x[]);  
      
    int main()  
    {  
        float M = 50;//背包所能容纳的重量  
        //这里给定的物品按单位价值减序排序  
        float w[] = {0,10,20,30};//下标从1开始  
        float v[] = {0,60,100,120};  
      
        float x[N+1];  
      
        cout<<"背包所能容纳的重量为:"<<M<<endl;  
        cout<<"待装物品的重量和价值分别为:"<<endl;  
        for(int i=1; i<=N; i++)  
        {  
            cout<<"["<<i<<"]:("<<w[i]<<","<<v[i]<<")"<<endl;  
        }  
          
        Knapsack(N,M,v,w,x);  
      
        cout<<"选择装下的物品比例如下:"<<endl;  
        for(int i=1; i<=N; i++)  
        {  
            cout<<"["<<i<<"]:"<<x[i]<<endl;  
        }  
      
        return 0;  
    }  
      
    void Knapsack(int n,float M,float v[],float w[],float x[])  
    {  
        //Sort(n,v,w);//这里假定w[],v[]已按要求排好序  
        int i;  
        for (i=1;i<=n;i++)  
        {  
            x[i]=0;//初始化数组x[]  
        }  
      
        float c=M;  
        for (i=1;i<=n;i++)//物品整件被装下,x[i]=1  
        {  
            if (w[i]>c)  
            {  
                break;  
            }  
            x[i]=1;  
            c-=w[i];  
        }  
      
        //物品i只有部分被装下  
        if (i<=n)  
        {  
            x[i]=c/w[i];  
        }  
    }  


     程序运行结果为:

贪心算法 背包问题

     算法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背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。