蒟蒻在线求调!这个贪心让人摸不着头脑!
查看原帖
蒟蒻在线求调!这个贪心让人摸不着头脑!
846554
XiMeng_2077楼主2023/8/29 18:07
大佬帮忙看看我到底哪里不够贪

#include<bits/stdc++.h>
using namespace std;
struct cost{     //每一堆金币的总重量,总价值,单价价格
	double weight,value;
	double average;
};
struct pack{     //当前背包的重量,价值
	double weight=0,value=0;
};
int main(){
	double n,bag;cost a[110];
	cin>>n>>bag;
	for(int i=1;i<=n;i++){   //读入每堆金币并计算单价价格
		cin>>a[i].weight>>a[i].value;
		a[i].average=a[i].value/a[i].weight;
	}
	for(int i=1;i<=n;i++){   //简单冒泡排序将单价价格最高的金币堆排到最后
		for(int j=1;j<=n-i;j++){
			if(a[i].average>a[j].average){
				cost p=a[i];a[i]=a[j];
				a[j]=p;
			}
		}
	}
	//拿取金币,背包够就全拿,不够则把背包装满
	pack temp;int cnt=n;
	while(temp.weight<bag){
		if(temp.weight+a[cnt].weight<bag){
			temp.weight+=a[cnt].weight;
			temp.value+=a[cnt].value;
		}else{
			double poor=bag-temp.weight;
			temp.weight+=poor;
			temp.value+=poor*a[cnt].average;
		}
		cnt--;
	}
	printf("%.2f",temp.value);
	return 0;//不太华丽的结束
}
2023/8/29 18:07
加载中...