金银岛（贪心算法实操）_金银岛 贪心

题目

 解答

#include <stdio.h>
#include <stdlib.h>
struct Kuangshi {
	int weight;
	int money;
	double danjia;
};
int cmp(const void *a, const void *b) {
	struct Kuangshi *aa = (struct Kuangshi *)a;
	struct Kuangshi *bb = (struct Kuangshi *)b;
	return (((aa->danjia) < (bb->danjia)) ? 1 : -1);
}
int main() {
	int k, w, s;
	int i, j;
	double Output[100];
	scanf("%d", &k);			//组数
 
	for ( i = 0; i < k; i++) {
		scanf("%d", &w);		//口袋上限
		scanf("%d", &s);		//矿石种类
		Kuangshi kuangshi[s];
		
		for ( j = 0; j < s; j++) {	//录入
			scanf("%d %d", &kuangshi[j].weight, &kuangshi[j].money);
			kuangshi[j].danjia = (double)kuangshi[j].money / (double)kuangshi[j].weight;
		}
		qsort(kuangshi, s, sizeof(kuangshi[0]), cmp); //从大到小排序
		int shengyu = w;			//剩余空间
		j = 0;
		Output[i]=0;
		do {
			shengyu -= kuangshi[j].weight;
			if(shengyu<0){
				Output[i]=Output[i]+(shengyu+kuangshi[j].weight)*kuangshi[j].danjia;
			}else	Output[i] += kuangshi[j].money;
			j++;
 
		} while (shengyu > 0&&j<s);
 
	}
	for(int i=0;i<k;i++){
		printf("%.2lf\n",Output[i]);
	}
	return 0;
}