贪心算法解决0-1背包问题

阳光穿透心脏的1/2处 2022-05-22 11:59 166阅读 0赞

背包问题描述如下: 已知

背包容量M=120

物品种类数n=10

各种物品的总效益pi(i=1,2,………10) : 50,60,70,80,90,80,70,60,50,40

各种物品的总重量wi(i=1,2………10) : 17,30,25,41,80,70,64,56,47,38

求: 各种物品所取重量占其总重量的比例xi(i=1,2,…..10),满足0<=xi<=1,

###     ###

按三种不同的量度标准分别计算所得最大总效益

1. 按效益值由大到小取物品

2. 按重量值由小到大取物品

3. 按比值pi/wi的值由大到小取物品

贪心算法思想

数据结构采用结构体来表示一个物品。按照各种量度标准排序物品。对于每一种排序结果，在背包容量内，选择量度最大的物品，继续选择次量度最大的物品，直到选到当前量度最大物品的重量大于背包剩余容量时（容不下），放入物品的一部分，这部分和背包剩余容量相等。打印出各物品是否被选择，或者被选择的比例。

程序代码

#include <iostream>
    #include <algorithm>
    #include <iomanip>
    #include <cstdio>
    using namespace std;
    struct form {
        int i;                       //为方便后序打印结果，设置物品序号
        int pi;
        int wi;
        float xi;
        int flag;                   //标志一整个物品被选取
        float floflag;              //标志物品被选取的那一部分
    };
    int bag, thingNum;
    int cmpPi( form a, form b )     //按效益值从大到小排序
    {
        return a.pi > b.pi;
    }
    int cmpWi( form a, form b )     //按重量从小到大排序
    {
        return a.wi < b.wi;
    }
    int cmpXi( form a, form b )     //按比例从大到小排序
    {
        return a.xi > b.xi;
    }
    void print( form *things, int thingNum )
    {
        printf( "物品序号   " );
        for( int i = 0; i < thingNum; i++ )
            printf( "%-6d", i );
        printf( "总效益\n           " );
        float ans = 0;                                           //总效益，边打印边计算
        for( int i = 0; i < thingNum; i++ ) {
            for( int j = 0; j < thingNum; j++ ) {
                if( things[j].i == i ) {
                    if( things[j].floflag != 0 ) {
                        printf( "%-6.3f", things[j].floflag );
                        ans += things[j].floflag * things[j].pi ;
                        things[j].floflag = 0;                       //置零初始化
                    }
                    else {
                        printf( "%-6d", things[j].flag );
                        if( things[j].flag == 1 )
                            ans += things[j].pi ;
                        things[j].flag = 0;                           //置零初始化
                    }
                    continue;
                }
            }
        }
        printf( "%-6.2f\n", ans );
        for( int i = 0; i < 100; i++ )
            printf( "-" );
        printf( "\n" );
    }
    void select( form *things )                                     //选取物品
    {
        int res = bag;
        for( int i = 0; i < thingNum; i++ ) {
            if( things[i].wi < res ) {
                things[i].flag = 1;
                things[i].floflag = 0;
                res -= things[i].wi;
            }
            else {
                things[i].flag  = 0;
                things[i].floflag = ( 1.0 * res ) / things[i].wi;
                break;
            }
        }
    }
    void value( form *things )
    {
        sort( things, things + thingNum, cmpPi );
        select( things );
        printf( "按效益值\n" ) ;
        print( things, thingNum );
    }
    void weight( form *things )
    {
        sort( things, things + thingNum, cmpWi );
        printf( "\n" );
        select( things );
        printf( "按重量\n" );
        print( things, thingNum );
    }
    void speVal( form *things )
    {
        sort( things, things + thingNum, cmpXi );
        cout << endl;
        select( things );
        printf( "按比值\n" ) ;
        print( things, thingNum );
    }
    int main( ) {
        printf( "请输入背包容量，物品数目：\n" );
        scanf( "%d%d", &bag, &thingNum );
        printf( "输入每个物品的效益和重量：\n" );
        form things[thingNum];
        for( int i = 0; i < thingNum; i++ ) {
            scanf( "%d%d", &things[i].pi, &things[i].wi );
            things[i].i = i;
            things[i].xi = 1.0 * things[i].pi / things[i].wi;
            things[i].flag = things[i].floflag = 0;           //初始化
        }
        value( things );                                       //按效益值
        weight( things );                                        //按重量值
        speVal( things );                                        // 按比值
        return 0;
    }

题目数据样例

120 10
    50 17
    60 30
    70 25
    80 41
    90 80
    80 70
    70 64
    60 56
    50 47
    40 38

输出样例

![70][]

[70]: /images/20220522/ea571f5a33084f26af445511e95a56dd.png