本文主要是介绍HDU1009-贪心-部分背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*转载请注明出处：乄心-小黄豆http://blog.csdn.net/wuxinxiaohuangdou*/
题目大意：一只老鼠要拿猫粮去各个仓库换豆子！
Input: M个猫粮，N个仓库。然后N行，每行第一个数为仓库的豆子数J[i]，第二个数为需要的猫粮F[i]。
Output::输出老鼠用猫粮能够换到的最大 豆子数！（可以在一个仓库取走a%（即一部分！））
这题是 经典的部分背包问题，关键在于要按照(价值与重量的比例)排序!
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
double M;
int N;
int i;
#define MAX 1010
class Node //代表仓库
{
public:double j,f,aver; //j为豆子数,f为需要的猫粮,ave为j/f即每付一个猫粮获得的豆子数（平均数）。bool operator<(const Node &temp)const{return temp.aver<aver;//把平均数从大到小排序。}
}a[MAX];
int main()
{while(true){cin>>M>>N;if(M==-1&&N==-1) break;double max_count=0;for(i=1;i<=N;i++) /*输入每个仓库数据*/{cin>>a[i].j>>a[i].f;a[i].aver=a[i].j/a[i].f;}sort(&a[1],&a[N+1]); //排序for(i=1;M!=0&&i<=N;i++) //去仓库用猫粮换豆子！{if(a[i].f<M) //当仓库需要的猫粮小于现在拥有的{max_count+=a[i].j; //就把豆子全部取走。M-=a[i].f; //付给相应的猫粮。}else {max_count+=a[i].aver*M; //否则当仓库需要的猫粮大于现在拥有的M=0; //就取走能取走的一部分，猫粮就用完啦！！}}printf("%.3lf\n",max_count);}return 0;
}不需要考虑
0 1
1 0
1 0
0 1
的情况不然WA。
这篇关于HDU1009-贪心-部分背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
