阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N \le 100)N(N≤100) 堆金币,第 ii 堆金币的总重量和总价值分别是 m_i,v_i(1\le m_i,v_i \le 100)mi,vi(1≤mi,vi≤100)。阿里巴巴有一个承重量为 T(T \le 1000)T(T≤1000) 的背包,但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割,分割完的金币重量价值比(也就是单位价格)不变。请问阿里巴巴最多可以拿走多少价值的金币?
第一行两个整数 N,TN,T。
接下来 NN 行,每行两个整数 m_i,v_imi,vi。
一个实数表示答案,输出两位小数
输入 #1
4 50 10 60 20 100 30 120 15 45
输出 #1
240.00
思路
由于每堆金币可以任意拆分,所以这道题其实是个贪心问题而不是背包问题。
先将每组数据按照性价比(自己算!)由大到小排序,
如果当前容量足够则全装,不够就装满。
tip:要注意的是,不够的情况要用剩余容量*当前性价比,性价比是浮点型,整型与浮点型相乘容易出错哦!要进行转换,为了避免错误,可以把相关变量都设置为浮点型!
#include<stdio.h> struct money//用结构体储存每堆金币信息 { double m;//重量 double v;//价值 double x;//性价比 }; int main() { int n,i,j; double t; scanf("%d %lf",&n,&t); struct money a[101],temp; for(i=0; i<n; i++) { scanf("%lf %lf",&a[i].m,&a[i].v); a[i].x=a[i].v/a[i].m;//每次输入金币信息就立刻求出这一堆的性价比 } for(j=0; j<n-1; j++)//因为是c语言,所以要手动排序!也可以打包为一个函数丢到外面 { for(i=0; i<n-1-j; i++) { if(a[i].x<a[i+1].x) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; } } } /* for(i=0; i<n; i++)//检查排序操作是否正确 printf("%d %d %f \n",a[i].m,a[i].v,a[i].x); */ double s=0,sum=0; for(i=0; i<n; i++) { s+=a[i].m; if(t>=s)//容量够全拿 { sum+=a[i].v; } else if(t<s)//容量不够装满 { sum+=(t-s+a[i].m)*a[i].x;//注意这里是和a[i].x相乘(它是浮点型) break; //为了防止类型转换出错,可以把所有相关数据改成浮点型 } } printf("%.2lf",sum); return 0; }