贪心算法---背包问题（物品可以分割问题）

74 阅读 0 评论 49 点赞

我是靠谱客的博主愉快大神，最近开发中收集的这篇文章主要介绍贪心算法---背包问题（物品可以分割问题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题背景：

有一天，阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时，远处突然出现一股烟尘，弥漫着直向上空飞扬，朝他这儿卷过来，而且越来越近。靠近以后，他才看清原来是一支马队，他们共有四十人，一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋，从丛林中一直来到那个大石头跟前，喃喃地说道：“芝麻，开门吧！”随着那个头目的喊声，大石头前突然出现一道宽阔的门路，于是强盗们鱼贯而入。阿里巴巴待在树上观察他们，直到他们走得无影无踪之后，才从树上下来。他大声喊道：“芝麻，开门吧！”他的喊声刚落，洞门立刻打开了。他小心翼翼地走了进去，一下子惊呆了，洞中堆满了财物，还有多得无法计数的金银珠宝，有的散堆在地上，有的盛在皮袋中。突然看见这么多的金银财富，阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所
积累起来的宝窟。为了让乡亲们开开眼界，见识一下这些宝物，他想一种宝物只拿一个，如果太重就用锤子凿开，但毛驴的运载能力是有限的，怎么才能用驴子运走最大价值的财宝分给穷人呢？阿里巴巴陷入沉思中……

问题分析：

假设山洞中有 n 种宝物，每种宝物有一定重量 w 和相应的价值 v，毛驴运载能力有限，
只能运走 m 重量的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢？
每次选取单位重量价值最大的宝物，也就是说每次选择性价比（价值/重量）最高的宝物，如果可以达到运载重量 m，那么一定能得到价值最大

算法设计：

（1）数据结构及初始化。将 n 种宝物的重量和价值存储在结构体 back（包含重量、价
值、性价比 3 个成员）中，同时求出每种宝物的性价比也存储在对应的结构体 back中，将其按照性价比从高到低排序。采用 sum 来存储毛驴能够运走的最大价值，初始化为 0。
（2）根据贪心策略，按照性价比从大到小选取宝物，直到达到毛驴的运载能力。每次选
择性价比高的物品，判断是否小于 c（毛驴运载能力），如果小于 c，则放入sum（已放入物品的价值）加上当前宝物的价值，c减去放入宝物的重量；如果不小于 c，则取该宝物的一部分 c* proportion[i]，c=0，程序结束。c减少到 0，则 sum 得到最大值。

在性价比排序的基础上，进行贪心算法运算。如果剩余容量比当前宝物的重量大，则可
以放入，剩余容量减去当前宝物的重量，已放入物品的价值加上当前宝物的价值。如果剩余容量比当前宝物的重量小，表示不可以全部放入，可以切割下来一部分（正好是剩余容量），然后令剩余容量乘以当前物品的单位重量价值，已放入物品的价值加上该价值，即为能放入宝物的最大价值。

测试数据：

输入：
6 19 //宝物数量，驴子的承载重量
2 8 //第 1 个宝物的重量和价值
6 1 //第 2 个宝物的重量和价值
7 9
4 3
10 2
3 4

输出：
24.6

代码如下：

#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

struct back{
    double weight;//重量
    double value;//价值
    double proportion;//性价比
}a[999];

bool beyond(back a,back b){
    return a.proportion >b.proportion;//性价比由大到小排序
}

int main()
{
    int number;//珠宝的种类
    double sum=0.0;//总价值
    double c;//驴最大载重量
    cin>>number>>c;
    for(int i=0;i<number;i++){//以次输入数据
        scanf("%lf",&a[i].weight);
        scanf("%lf",&a[i].value);
        a[i].proportion = a[i].value / a[i].weight;
    }

    sort(a,a+number,beyond);//按性价比由大到小排序

    for(int j=0;j<number;j++){
        if(c>=a[j].weight){//宝物的重量小于或等于驴的载重量
            c-=a[j].weight;//装上该宝物之后，驴的剩余载重量
            sum+=a[j].value;//宝物的价值
        }else{//宝物的重量大于驴的载重量
            sum+= c * a[j].proportion;//分割宝物
            break;
        }
    }
    printf("%.1lfn",sum);
    cout<<sum;
    return 0;
}