算法——Buyer

题目描述

哆啦A梦班级举办个party,当然吃的东西必不可少,哆啦A梦负责采购任务,他得到了一份清单,上面注明不同食品的受欢迎程度,哆啦A梦需要用一定的价钱尽可能达到的更大的受欢迎程度!例如,瓜子的受欢迎程度为20,瓜子的价钱是50元,那么如果哆啦A梦选择买瓜子,将花费50元,但受欢迎程度增加了20。为了避免食品单调性,每种食品只能买一份,不能重复购买。 现在哆啦A梦需要知道如何采购才能达到最大的受欢迎程度,你能帮助他吗?

输入

输入数据为多组,每组输入的第一行有两个正整数M和N(M<100&&N<1000),分别为哆啦A梦可以支配的钱数和清单上的可选择的物品种类。 接下来的N行每行有两个正整数,分别为每种物品的价钱和它的受欢迎程度(编号为1到N)。

输出

如果存在物品购买,那么输出的第一行为能够达到的最大的受欢迎程度。第二行为需要购买的物品的编号(如果有多种可能,输出字典序靠前的那种),空格分隔每个数字;如没有物品可以购买,输出只有一行,为数字0。

样例输入

10 4
100 5
5 5
5 5
10 10

样例输出

10
2 3

代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct{
	int price;
	int popular;
	int i;
}Gs;
Gs p[1000];
bool cmp(Gs p1, Gs p2){
	return (p1.popular /p1.price )>(p2.popular /p2.price );
}
int main(){
	int ans, s ,a[1000];
	int M,N;
	while(cin>>M>>N){
		ans = 0, s = 0;
		for(int i = 0; i < N; i++){
			cin>>p[i].price >>p[i].popular ;
			p[i].i = i + 1;
		}
		sort(p, p + N, cmp);
		for(int i = 0; i < N && M >0; i++){
			if(M - p[i].price < 0) continue;
			M -= p[i].price ;
			ans += p[i].popular ;
			a[s++] = p[i].i ;
		}
		if(s == 0) cout<<"0"<<endl;
		else {
			cout<< ans << endl;
			sort( a, a+s);
			for(int i = 0; i < s - 1; i++)
				cout<<a[i] <<' ';
			cout<<a[s-1]<<endl;
		}
	}
	return 0;
} 

思路

1.第二次上手发现这道题是比较简单的;

2.主要的突破口是要搞清楚如何在有限的money内得到最大的受欢迎程度;

3.首先,单个物品的受欢迎程度与其价格之比进行排序,比值越大,性价比更高;

4.然后,包里的money是否可以买到性价比高的物品,如果可以,包里的money就会减少啦,反之,就跳过,重复这条操作;

5.要注意的是,还要输出物品的编号,代码里面是会进行排序的,可能会打乱原有的顺序,要怎么解决呢?可以在结构体里面添加物品序号 i ,并在输入时进行设置。

上一篇:Javashop 7.0 商城Https协议修改部分


下一篇:程序的修改!