给定 N 种物品和一个背包。物品 i 的重量是 W i ，价值为 V i ；背包的容量为 V。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品，对每种物品可以选择：全部装入或装入部分，且不能重复装入。输入数据的第一行分别为：背包的容量 V，物品的个数 N。接下来的 N 行表示 N 个物品的重量和价值。输出为最大的总价值。

输入格式:

第一行连个整数，分别是V和N(<=1000) 接下来N行，每行分别为 W i 和 V i

输出格式:

输出为最大的总价值（保留两位小数）

输入样例:

15 4
3 5
4 6
5 7
7 12

输出样例:

24.40

作者:严华云
单位:湖州师范学院
代码长度限制:16 KB
时间限制:400 ms
内存限制:64 MB

#include<bits/stdc++.h>
using namespace std;
class items{
	public:
		double weight;
		double value;
		double average;
};
int main(){
	int v,n,s;
	double sum=0.0;
	cin>>v>>n;
	class items sp[n];
	for(int i=0;i<n;i++){
		cin>>sp[i].weight>>sp[i].value;
		sp[i].average=sp[i].value/sp[i].weight;
	}
	sort(sp,sp+n,[](class items a,class items b){return a.average>b.average;});
	for(int i=0;i<n;i++){
		s = s + sp[i].weight;
		if(s>v){
			s = s-sp[i].weight;
			sum = sum + (v-s)*sp[i].average;
		}
		else{
			sum = sum + sp[i].value;
		}
	}
	printf("%.2lf",sum);
}

注：在dev c++运行时需设置编译环境