【hdoj_2111】SavingHDU

题目：http://acm.hdu.edu.cn/showPRoblem.php?pid=2111

题目理解：给出一个口袋的容量，若干种宝物的单价和体积，单个的宝物可以分割，待求的是最多能装价值多少的宝物.

思路：宝物可以分割，所以如果宝物足够多的话，口袋可以装满.因此，先对所有宝物按照价格递减排序，然后从高价的宝物开始，把它们放进口袋，直到宝物装完了或者口袋装满了为止.

装的过程中会遇到两种情况：

1.某种宝物的体积小于口袋的体积，则将这种宝物全部装进口袋，更新口袋的剩余容积.

2.某种宝物的体积大于口袋的体积，则将这种宝物的一部分装进口袋是口袋装满.

C++代码如下

#include<iostream>#include<algorithm>using namespace std;struct Treasure//将宝物看多 结构体 {	int price;	int volume;};bool cmp(Treasure t1,Treasure t2){	return t1.price > t2.price;//用于将宝物按照价格递减顺序排序 }int main(){	int V,n;	while(cin>>V)	{		if(V==0) break;		cin >> n;		Treasure *T = new Treasure[n];		for(int i=0;i<n;i++)			cin >> T[i].price >> T[i].volume;		sort(T,T+n,cmp);//排序 		int result = 0;		for(int i=0;i<n;i++)		{			if(V==0)	break;//口袋满了，退出 			if(V>T[i].volume)			{				result += T[i].price * T[i].volume;					V = V - T[i].volume;//更新口袋数据 			}			else			{				result += T[i].price * V;				V = 0;//更新口袋数据 			}		}		cout << result << endl;	} 		return 0;}注意：上述代码提交会出现错误提示，删掉所有的注释再提交，可以通过.