这道题是真的不会写,思路一点也没有
问题描述
小鱼儿在一次探险途中发现了一个山洞,并且在这个山洞里找到了宝藏,可是小鱼儿发现想要把宝藏全部带走是不可能的(因为他只带了一个袋子),不过很快他就发现每个宝物旁边都有几个字,上面写着宝物的体积和价值,而且这些宝物可以分割成任意大小。小鱼儿想知道如何选取宝物,才能使带走宝物的价值最大。
预置代码
输入
第一行有两个整数v和n,表示袋子的容量和宝物的数量。(0<n<=100,0<v<=10000)
接下来n行每行两个整数,分别表示宝物的体积和价值。
输出
在单独的一行中输出一个数,表示能够带走宝物的最大价值,结果保留两位小数。
输入样列
10 3
10 30
11 55
4 30
输出样例
60.00
提示
出处
ymc
#include<bits/stdc++.h>
using namespace std;
struct bao{
int t;
double m;
double x;
}p[1000];
int main()
{int v,n;
scanf("%d%d",&v,&n);
for(int i=1;i<=n;i++)
{int a;
double b;
scanf("%d %lf",&a,&b);
p[i].m=b;
p[i].t=a;
p[i].x=b/a;
}
for(int i=1;i<=n;i++)
{for(int j=i+1;j<=n;j++)
{if(p[i].x<p[j].x)
{swap(p[i],p[j]);
}
}
}
int V=v;
double max;
if(v>p[1].t)
{max=p[1].m;
V=v-(p[1].t);
}
else
{
max=v*p[1].x;
V=0;
}
for(int j=2;j<=n;j++)
{
if(V>=p[j].t)
{
max=max+p[j].m;
V=V-p[j].t;
}
else
{max=max+p[j].x*V;
break;
}
}
printf("%.2lf\n",max);
return 0;
}
单位体积价值大的宝物优先带