题目来源和说明

题目来源自王道考研！在这一节中主要梳理的四贪心的思想，即总是选择“当前最好的选择”。希望通过本节内容掌握贪心的一些基本思想。

题目描述

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

样例

输入：
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

输出：
13.333
31.500

简要分析

题目的大意如下：有m元钱，n种物品；每种物品有j磅，总价值f元，可以使用0到f的任意价格购买相应磅的物品，例如使用0.3f元，可以购买0.3j磅物品。要求输出用m元钱最多能买到多少磅物品。

一种直观的思路是，每次都买剩余物品中性价比（即重量价格比）最高的物品，直到该物品被买完或者耗尽。若该物品已经被买完了，则我们继续在剩余的物品种寻找性价比最高的物品，重复该过程；若金钱耗尽，则交易结束。其实这就是贪心的思想。

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

struct goods{
	double j; //该物品的重量 
	double f; //该物品的总价值 
	double s; //该物品性价比 
	bool operator<(const goods &A) const {
		return s>A.s; 
	}
}buf[1000];

int main() {
	double m;
	int n;
	while(scanf("%lf%d",&m,&n)!=EOF) {
		if(m==-1 && n==-1) break;
		for(int i=0;i<n;i++) {
			scanf("%lf%lf",&buf[i].j,&buf[i].f);
			buf[i].s=buf[i].j/buf[i].f;
		}
		sort(buf,buf+n);
		int idx=0; //当前货物的下标
		double ans=0; //累加所能得到的总重量
		while(m>0&&idx<n) { //循环条件：还有物品剩余还有钱 
			if(m>=buf[idx].f) { //钱多全买 
				ans+=buf[idx].j;
				m-=buf[idx].f; 
			} 
			else { //钱不够买一部分 
				ans+=buf[idx].s*m;
				m=0; 
			}
			idx++;
		} 
		printf("%.3f\n",ans); 
	}
	return 0;
}

同类题目

  1. 看电视

简要分析

基于贪心的思想，我们首先考虑这样一个问题：第一个节目我们应该选什么。我们选开始时间最早的？假如A[0,5],B[1,2],C[3,4]。显然选择最先开始的节目并不一定能够得到最优解。那选持续时间最短的呢？假如A[0,10],B[11,20],C[9,12].显然选择时间最短的节目并不一定能够得到最优解。那选择结束时间最早的呢？这个方案是可以得到最优解的。我们可以试着证明该命题：最优解中，第一个观看的节目一定是所有节目里借宿时间最早的节目。因为按照优先选择借宿时间最早的节目，我们所观看的第一个节目一定是所有节目里借宿时间最早的。同样的我们用反证法来证明：假设命题：最优解种，第一个观看的节目A[s1,e1]不是所有节目时间里结束时间最找的节目，即存在节目B[s2,e2]，其中e2<e1。那么B节目一定不再该解当中，因为若在，其顺序一定在A节目之前，但是A节目已经假定为第一个节目，所以B节目一定没被我们收看。那么，我们可以将该节中的第一个节目A换成节目B，该替换保证是合法的，即去掉B节目以后，其他节目的播出时间一定不会与节目A冲突。做这样的替换以后，原解与当前解除了第一个节目不同，其他节目安排完全相同。那么这两组解所包含的节目数是一模一样的，该解也是最优解。

由以上证明可见，如果最优解的第一个节目并不是结束最早的节目，那么我们可以直接用结束时间最早的节目代替该解中的第一个节目，替换后的解也是最优解。这样，我们就可以得出当第一个节目选择所有节目活动中借宿最早的节目，这样一定可以得到最优解。

C++代码

#include<iostream>
#include<algorithm>

using namespace std;

struct activity{
    int st;
    int en;
    bool operator <(const activity& A) const {
        return en<A.en;
    }
}buf[100];

int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        if(n==0) break;
        for(int i=0;i<n;i++) {
            scanf("%d%d",&buf[i].st,&buf[i].en);
        }
        sort(buf,buf+n); //按照借宿时间升序排序
        int currentTime=0,ans=0;
        for(int i=0;i<n;i++) {
            if(currentTime<=buf[i].st) {
                currentTime=buf[i].en;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
}
  1. 迷瘴

https://blog.nowcoder.net/n/de28b9c957224216ac95ccc346bbd2ec

简要分析

基于贪心的思想，我们还是考虑这样一个问题：第一个浓度应该怎么选，为了不大于w浓度，而且体积更大。因此应该选择浓度最低的。即最优解的第一个浓度一定是最低的。我们试着证明这个命题：最优解中，第一个选择的浓度一定是所有浓度中最低的。我们用反证法：假设命题：最优解中第一个浓度不是所有浓度最低的，即存在浓度s2<s1，并且s2不再该解当中。那么我们将s1换成更低浓度的s2，仍然不会超过w，因此，这种情况已经与最优解达到了相同的体积，也是最优解。即局部优先选择最低浓度的一定是最优解！

C++代码

//该问题没有找到在线判定平台，代码仅在本地跑通，如有错误，欢迎评论~
#include<iostream>
#include<algorithm>
using namespace std;

int a[105];
int main() {
	int m,n;
	int v,w;
	scanf("%d", &m);
	while(m--) {
		scanf("%d%d%d",&n,&v,&w);
		for(int i=0;i<n;i++) 
			scanf("%d",&a[i]);
		sort(a,a+n);
		if(a[0]>w) printf("0 0.00\n");
		else {
			double currentRho=0;
			int currentV=0;
			double before=0;
			for(int i=0;i<n;i++) {
				before=currentRho;
				currentRho=(currentRho*currentV+a[i]*v)/(currentV+v);
				currentV+=v;
				if(currentRho>w) break;
			}
			if(currentRho>w) printf("%d %.2f\n",currentV-v,before/100);
			else printf("%d %.2f\n",currentV,currentRho/100);
		}
	}
	return 0;
}

3.Repair the wall

4.To fill or not to fill