部分背包问题

xiaoxiao2021-03-01  9

HDU-1009-FatMouse’ Trade

肥鼠准备了 M 磅的猫粮,准备和看管仓库的猫交易,仓库里装有他最喜爱的食物 Java 豆。 仓库有 N 个房间。第 i 间房包含了 J[i] 磅的 Java 豆,需要 F[i] 磅的猫粮。肥鼠不必为了房间中的所有 Java 豆而交易,相反,他可以支付 F[i] * a% 磅的猫粮去交换得到 J[i] * a% 磅的 Java 豆。这里,a 表示一个实数。 现在他将这项任务分配给了你:请告诉他,能够获得的 Java 豆的最大值是多少。

输入 输入包含多组测试数据,对于每组测试数据,以包含了两个非负整数 M 和 N 的一行开始。接下来的 N 行,每行相应包含了两个非负整数 J[i] 和 F[i]。最后一组测试数据是两个 -1。所有的整数均不超过 1000。 输出 对于每组测试数据,在单独的一行中打印一个实数,精确到小数点后 3 位数,表示肥鼠能够取得的 Java 豆的最大值。

示例输入 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1

示例输出 13.333 31.500

分析:就是一个部分背包的模板体,用一下结构体就行了,也是个贪心,排下序然后从最大开始算。

#include<stdio.h> #include<algorithm> using namespace std; struct stu{ double xjb; //这个是每个房间的性价比 double j,f; //分别是需要的猫粮和豆子 }de[2000]; bool cmp(stu a,stu b) { return a.xjb > b.xjb; //排序 } int main() { int n,i; double m,F,J; while(scanf("%lf%d",&m,&n)!=EOF) { double sum = 0; if(m==-1&&n==-1) break; for(i = 0;i < n; i++){ scanf("%lf%lf",&de[i].j,&de[i].f); de[i].xjb = de[i].j/de[i].f; } sort(de,de+n,cmp); for(i = 0;i < n; i++) { if(m >= de[i].f){ //这个需要比较一下 sum += de[i].j; m -= de[i].f; } else{ sum += de[i].j*(m/de[i].f); break; } } printf("%.3lf\n",sum); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-3100032.html

最新回复(0)