贪心算法（一）

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

代码如下：

#include<stdio.h>

#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+1);
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].j*m/buf[idx].f;
m=0;
}
idx++;
}
printf("%.3lfn",ans);
}
return 0;
} 

最后

以上就是平常悟空最近收集整理的关于贪心算法（一）的全部内容，更多相关贪心算法（一）内容请搜索靠谱客的其他文章。