P2240 【深基12.例1】部分背包问题

青旅半醒 2022-11-14 00:49 140阅读 0赞

## 题目描述 ##

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

## 输入格式 ##

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

接下来  N N N 行，每行两个整数  m i , v i m\_i,v\_i mi,vi。

## 输出格式 ##

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

**输入输出样例**  
**输入**

4 50
    10 60
    20 100
    30 120
    15 45

**输出**

240.00

--------------------

这只是部分背包还比较好做，贪心足矣。

说白了就是比性价比。

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    using namespace std;
    struct gold
    { 
        int c, w;
    }; //定义结构体，c代表价值，w代表重量
    gold item[1010];
    bool cmp(gold a, gold b)
    { 
        return a.w * b.c > b.w * a.c;
    } // 比的是单位价格!
    int N, T;
    double ans = 0.0;
    int main()
    { 
        cin >> N >> T;
        for (int i = 0; i < N; i++)
        { 
            cin >> item[i].c >> item[i].w;
        }
        sort(item, item + N, cmp); //输入后排序
        for (int i = 0; i < N; i++)
        { 
            if (T <= item[i].c) // 虽然装不下，但是性价比最高，装满了也是值得的
            { 
                ans += (double)item[i].w / item[i].c * T * 1.0; //1.0可能加的很无用
                // T = 0;
                break; //如果背包容量不够放下所有这种金币，就把背包装满，然后break。
            }
            else
            { 
                ans += item[i].w;
                T -= item[i].c;
            } //够的话全装进去，因为当前最值得
        }
        printf("%.2lf", ans); //保留2位小数输出
        return 0;
    }