本文主要是介绍P2240 【深基12.例1】部分背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
这个题有个容易的误区，最开始的时候我直接选择了总价值最多的物品，结果是220，和答案不一致。仔细看了题目才发现应该是按照单位价值的大小排序，先选择单位价值最大的。
代码1：得了20分
#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;int n,t;
struct node{int m,v;double aver;
};
node a[110];
int summ;//记录已经装了多少
double value;//记录最终价值 bool cmp(node aa,node bb){return aa.aver > aa.aver;
}int main()
{scanf("%d%d",&n,&t);for(int i=0;i<n;i++){scanf("%d%d",&a[i].m,&a[i].v);a[i].aver = a[i].v * 1.0 / a[i].m * 1.0;}sort(a,a+n,cmp);int i=0; while(summ + a[i].m < t && i < n){summ += a[i].m;value += a[i].v * 1.0; i++;} value += a[i].aver * (t - summ);printf("%.2lf",value);return 0;
}
结果：
代码2：
#include<bits/stdc++.h>
using namespace std;
struct node{//定义结构体 double w;//重量 double v;//价值 double p;//性价比
}a[105];
int n;
double sum,c;
inline bool cmp(node a,node b){return a.p >b.p;//性价比从大到小排序
}
int main(){cin>>n>>c;for(register int i=1;i<=n;++i){cin>>a[i].w>>a[i].v;a[i].p=a[i].v/a[i].w;//性价比=价格/重量 }sort(a+1,a+n+1,cmp);//将性价比排序 for(register int i=1;i<=n;++i){if(c>=a[i].w){//金币的重量小于或等于背包的承重量c-=a[i].w;//装上该堆金币后背包的剩余承重量 sum+=a[i].v;//金币的价值 }else{sum+=c*a[i].p;//如果装不下就分割金币 break;}}printf("%.2f",sum);//保留小数点后两位输出return 0;
}这篇关于P2240 【深基12.例1】部分背包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
