【题目来源】
洛谷：P2240 【深基12.例1】部分背包问题 - 洛谷 (luogu.com.cn)
【题目描述】
阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 \(N(N\le 100)\) 堆金币，第 \(i\) 堆金币的总重量和总价值分别是 \(m_i,v_i(1\le m_i,v_i\le 100)\)。阿里巴巴有一个承重量为 \(T(T\le 1000)\) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？
【输入】
第一行两个整数 \(N,T\)。
接下来 \(N\) 行，每行两个整数 \(m_i,v_i\)。
【输出】
一个实数表示答案，输出两位小数
【输入样例】
4 50
10 60
20 100
30 120
15 45
【输出样例】
240.00
【解题思路】
【算法标签】
《洛谷 P2240 部分背包问题》 #贪心#
【代码详解】
#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;// 定义硬币结构体
struct coin
{int m; // 硬币的质量int v; // 硬币的价值double avg; // 单位质量的价值
} cs[105]; // 最多105个硬币// 自定义排序比较函数：按单位价值从高到低排序
bool cmp(coin c1, coin c2)
{return c1.avg > c2.avg;
}int main()
{int n, t, mark = 0; // n:硬币数量, t:背包容量, mark:当前处理的硬币索引double ans = 0; // 最终获得的总价值// 输入硬币数量和背包容量cin >> n >> t;// 输入每个硬币的质量和价值，并计算单位价值for (int i = 0; i < n; i++) {cin >> cs[i].m >> cs[i].v;cs[i].avg = 1.0 * cs[i].v / cs[i].m;}// 按单位价值从高到低排序sort(cs, cs + n, cmp);// 贪心算法：优先拿单位价值高的硬币while (t >= cs[mark].m && mark < n) {t -= cs[mark].m; // 减去已拿硬币的质量ans += cs[mark].v; // 加上已拿硬币的价值mark++; // 处理下一个硬币}// 处理剩余容量（拿部分硬币）if (mark < n && t > 0) ans += t * cs[mark].avg; // 按比例拿部分硬币// 输出结果，保留两位小数printf("%.2f", ans);return 0;
}
【运行结果】
4 50
10 60
20 100
30 120
15 45
240.00