贪心算法求解背包问题-蒲公英云

贪心算法求解背包问题

贪心算法，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

解题的一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。

在这里我们用贪心法来解决可切割物品的背包问题，首先选择贪心属性，比较所有物品的单价；其次，按照物品单价将所有物品从大到小进行排序；最后，优先把单价高的物品装进背包。将单价第一高的物品尽可能全部装入背包，如果背包容量还有剩余，则继续将单价第二高的物品尽可能装进背包…以此类推，就可以求出背包问题的最优解。

在这个问题中，可以使用结构体来储存物品及其价格与单价的信息，在这里使用选择排序按照单价对结构体成员进行排序。

#include<stdlib.h>
#include<time.h>
#include<stdio.h>
const int N=10;
double value=0;
struct goods{
    int No;//编号
    int w;//重量
    int v;//价值
    double avg;//单位重量的价值
};
void selectsort(goods g[]){
    //选择排序
    for(int i=0;i<N;i++)
        for(int j=i;j<N;j++)
            if(g[i].avg<g[j].avg){
                goods x;
                x=g[i];
                g[i]=g[j];
                g[j]=x;
            }
}
double greedy_tui(goods g[],int c)
{
    double value=0;
    for(int i=0;i<N;i++){
    //对排好序的物品按顺序进行贪心
        if(c<g[i].w){
            if(c>0){
                value=value+c*g[i].avg;
                g[i].w=g[i].w-c;
                c=0;
            }else break;
        }else{
            value=value+g[i].v;
            c=c-g[i].w;
        }
        //Found!!!!!
        //先装哪个？如何判断是否满了？
        //什么时候需要分割物品？如何记录最大价值？    
    }
    return value;
}
int main()
{
    //srand((unsigned)time(NULL));
    int c=rand()%50;//初始化背包容量
    printf("背包最大承重:%d公斤\n",c);
    goods g[N];    
    for(int i=0;i<N;i++)//初始化物品参数
    {
        g[i].No=i;
        g[i].w=rand()%10+1;
        g[i].v=rand()%10+1;
        g[i].avg=g[i].v;
        g[i].avg=g[i].avg/g[i].w;
        printf("物品%d重%d公斤,价值%d元\n",g[i].No,g[i].w,g[i].v);
    }
        selectsort(g);
    printf("排序后：\n");
    for(int i=0;i<N;i++) printf("物品%d重%d公斤,价值%d元\n",g[i].No,g[i].w,g[i].v);
    printf("递推能装入背包的最大价值为%f元\n",greedy_tui(g,c));
    return 0;
}