背包问题的贪心算法

算法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;       
}     

运行效果：

打赏