部分背包问题-贪心算法

问题描述

有一个调制饮品比赛

参赛者拥有容量为 c ml的杯子，可任选不超过体积上限的饮料进行混合
调制饮品价格为各所使用饮料的价格之和，所得饮品价格之和最高者获胜

每种饮品有对应的价值和体积，应该如何使调制的饮品价格最高？

输入数据

第一行输入物品数量n和背包容量c。
接下来是n行数据，表示每个饮料的价值的体积。

输入输出样例

输入：

5 800
60 600
10 250
36 200
16 100
45 300

输出：

117

思路分析

这是一个典型的贪心问题，要求调制的饮品价格最高。
我们采用最高性价比优先的方法

性价比 = 价格/体积
优先选择高性价比饮料全部装入，尽可能装满杯子

首先对n种饮品按照性价比降序排序，这里对于饮品我使用了结构体类型，结合sort函数即可实现。
定义一个ans表示当前饮品的价值,并赋初值为0，接下来对排好序的饮品进行遍历循环，循环条件为c>0(杯子还有剩余体积)且i<n.
while循环体内，若当前饮品体积小于剩余体积c,则将其全部放入,c=c-当前饮品体积；
否则，放入剩余体积c的该饮品，也就是将剩下的体积全部放入当前饮品，c=0。

代码样例

//
//  main.cpp
//  部分背包问题
//
//  Created by MacBook Pro on 2021/4/19.
//

#include <iostream>
#include<algorithm>
using namespace std;
struct goods//表示商品
{
    float weight;//重量
    float value;//价值
    float ratio;//性价比
};
bool cmp(goods x,goods y)
{
    return x.ratio>y.ratio;
}
int FractionalKnapsack(int n,goods a[],int c)//求解背包问题
{
    sort(a,a+n,cmp);//按照性价比降序排序
    int ans=0;
    int i=0;
    while(c>0&&i<n)
    {
        if(a[i].weight<=c)//选择商品i的全部
        {
            ans+=a[i].value;
            c-=a[i].weight;
        }
        else//选择剩余c体积的商品i
        {
            ans+=a[i].value*(c/a[i].weight);
            c=0;
        }
        i++;
    }
    return ans;
}
int main()
{
    int n,i,c; //c为背包容量
    cin>>n>>c;
    goods a[n];//定义结构体数组
    for(i=0;i<n;i++)
    {
        cin>>a[i].value>>a[i].weight;
        a[i].ratio=(float)a[i].value/(float)a[i].weight;//ratio=value/weight
    }
    cout<<"最优解为"<<FractionalKnapsack(n,a,c)<<endl;
    return 0;
}