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

原题网址：【深基12.例1】部分背包问题 - 洛谷

题解：

由题意可得，每一堆金币都有个比值（总价值/重量）。按比值的大小装进背包里面，第一次选比值最大的，第二次选第二大的，保证每次选择时都是最大的（对于此刻来讲是最大的，并不是全体最大的）。依次选下来，当背包满的时候就停止。

AC代码：


#include <bits/stdc++.h>
#define run(i,n) for (int i = 1; i <= n; i++)
#define cin std::cin
#define cout std::cout
#define ll long long
#define endl "\n"
using namespace std;
const int N = 2e6 + 10;
 
struct str {
	double a; //重量
	double b; //价值
	double c; //比值
} x[N];
 
bool cmp(struct str x, struct str y) {
	return x.c > y.c;
}
 
int main() {
	int T, n; //T 几堆 n 背包总容量
	cin >> T >> n;
	run(i, T) { //输入
		cin >> x[i].a >> x[i].b;
		x[i].c = x[i].b / x[i].a;
	}
 
	sort(x + 1, x + T + 1, cmp); //排序
 
	double sum = 0;
 
	run(i, T) {
		if (n >= x[i].a) { //能够一次性放进背包里的
			sum += x[i].b;
			n -= x[i].a;
		} else { //分割放进来的
			sum += n * x[i].c;
			break; //轮到分割的时候就是最后一次了
		}
 
	}
 
	printf("%.2lf", sum);
 
	return 0;
}

二、合并果子

题目：

        在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

        每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

        因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

        例如有 3 种果子，数目依次为 1 ， 2 ， 9 。可以先将 1 、 2 堆合并，新堆数目为 3，耗费体力为 3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12。所以多多总共耗费体力 =3+12=15 。可以证明 15 为最小的体力耗费值。

原题网址：[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷

题解：

从贪心的角度来，每一次选取最少的两堆合并，那么花费的体力就最小，但合并后这一堆并不一定是剩下这一堆里面最少的两堆之一，那么我就得重新找......以此类推。按照基本想法来就是排序后将最少的两堆合并，再排序，再合并，再排序......但有个容器可以方便执行，那就是优先队列，放入队列中就已经排好了。

贪心是一种思想，而对于实现可以用很多种的方法，可能会更加方便简介。

AC代码：


#include <bits/stdc++.h>
#define cin std::cin
#define cout std::cout
#define ll long long
#define endl "\n"
using namespace std;
 
priority_queue<int, vector<int>, greater<int>>q; //创建优先队列
int n, ans, x;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> x, q.push(x); //推入队列
	while (q.size() >= 2) {
		int a = q.top(); //取头值赋给a
		q.pop(); //推出头
		int b = q.top();
		q.pop();
		ans+=a+b;
		q.push(a+b);
	}
	cout<<ans<<endl;
 
	return 0;
}

三、国王游戏

题目：

        恰逢 H 国国庆，国王邀请 n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

        国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

原题网址：[NOIP2012 提高组] 国王游戏 - 洛谷

题解：

这是一道经典的相邻交换法的贪心题目。

第 $i$ 个人左右手分别是 $a_{i}$ , $b_{i}$ 。用 $s$ 代表第 $i$ 个人前面所有 $a_{i}$ 的乘积，那么第 $i$ 个人得到的金币为 $\frac{s}{b_{i}}$ ，第 $i+1$ 个人得到的金币为 $\frac{s*a_{i}}{b_{i+1}}$ 。

如果我们交换第 $i$ 个大臣与第 $i+1$ 个大臣，那么此时的第 $i$ 个大臣得到的奖赏就是 $\frac{s}{b_{i+1}}$ ，第 $i+1$ 个大臣得到的奖赏就是 $\frac{s*a_{i+1}}{b_{i}}$ 。

没交换前的最大的金币 $\max \left ( \frac{s}{b_{i}} ,\frac{s*a_{i}}{b_{i+1}}\right )$ ,交换后的最大金币 $\max \left ( \frac{s}{b_{i+1}} ,\frac{s*a_{i+1}}{b_{i}}\right )$ ；

那么排序的顺序就是 $\max \left ( \frac{s}{b_{i}} ,\frac{s*a_{i}}{b_{i+1}}\right )$ $<$ $\max \left ( \frac{s}{b_{i+1}} ,\frac{s*a_{i+1}}{b_{i}}\right )$ ；

那么可以化简一下，将两边约分 $s$ ,为 $\max \left ( \frac{1}{b_{i}} ,\frac{a_{i}}{b_{i+1}}\right )$ $<$ $\max \left ( \frac{1}{b_{i+1}} ,\frac{a_{i+1}}{b_{i}}\right )$ ；

化整，为 $\max \left (b _{i+1},a_{i}*b_{i} \right )$ $<$ $\max \left (b _{i},a_{i+1}*b_{i+1} \right )$ ；

因为 $b_{i+1}<a_{i+1}*b_{i+1}$ , $b_{i}<a_{i}*b_{i}$ ,所以其实比较 $a_{i}*b_{i}$ 和 $a_{i+1}*b_{i+1}$ 即可。

另外此题还与高精度有关，在此不做多赘述。

排序代码：


struct str {
	ll a, b, c; //a 左手 b 右手
} x[N];
 
 
//第一种
bool cmp(struct str a, struct str b) {
	return max(b.b, a.a * a.b) < max(a.b, b.a * b.b);
}
 
//第二种 （缩减进阶）
bool cmp(struct str a, struct str b) {
	return max(a.a * a.b, b.a * b.b);
}

习题：

【算法1-5】贪心 - 题单 - 洛谷

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】