金银岛（贪心算法实操）

金银岛（贪心算法实操）"/>

金银岛（贪心算法实操）

题目

 解答

#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;
}