贪心牛奶之部分背包问题

本文主要是介绍贪心牛奶之部分背包问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目来源：洛谷

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N \le 100)N(N≤100) 堆金币，第 ii 堆金币的总重量和总价值分别是 m_i,v_i(1\le m_i,v_i \le 100)mi​,vi​(1≤mi​,vi​≤100)。阿里巴巴有一个承重量为 T(T \le 1000)T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 N,TN,T。

接下来 NN 行，每行两个整数 m_i,v_imi​,vi​。

输出格式

一个实数表示答案，输出两位小数

输入输出样例

输入 #1

4 50
10 60
20 100
30 120
15 45

输出 #1

240.00

思路

由于每堆金币可以任意拆分，所以这道题其实是个贪心问题而不是背包问题。

先将每组数据按照性价比（自己算！）由大到小排序，

如果当前容量足够则全装，不够就装满。

tip：要注意的是，不够的情况要用剩余容量*当前性价比，性价比是浮点型，整型与浮点型相乘容易出错哦！要进行转换，为了避免错误，可以把相关变量都设置为浮点型！

#include<stdio.h>
struct money//用结构体储存每堆金币信息
{
    double m;//重量
    double v;//价值
    double x;//性价比
};
int main()
{
    int n,i,j;
    double t;
    scanf("%d %lf",&n,&t);
    struct money a[101],temp;
    for(i=0; i<n; i++)
    {
        scanf("%lf %lf",&a[i].m,&a[i].v);
        a[i].x=a[i].v/a[i].m;//每次输入金币信息就立刻求出这一堆的性价比
    }
    for(j=0; j<n-1; j++)//因为是c语言，所以要手动排序！也可以打包为一个函数丢到外面
    {
        for(i=0; i<n-1-j; i++)
        {
            if(a[i].x<a[i+1].x)
            {
                temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
            }
        }
    }
    /*
    for(i=0; i<n; i++)//检查排序操作是否正确
        printf("%d  %d  %f   \n",a[i].m,a[i].v,a[i].x);
    */
    double s=0,sum=0;
    for(i=0; i<n; i++)
    {
        s+=a[i].m;
        if(t>=s)//容量够全拿
        {
            sum+=a[i].v;
        }
        else if(t<s)//容量不够装满
        {
            sum+=(t-s+a[i].m)*a[i].x;//注意这里是和a[i].x相乘（它是浮点型）
            break;                  //为了防止类型转换出错，可以把所有相关数据改成浮点型
        }
    }
    printf("%.2lf",sum);
    return 0;
}

这篇关于贪心牛奶之部分背包问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！