编辑代码

#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<time.h>
using namespace std;

struct Goods{
	double price;
	double weight;
};

bool price(Goods A,Goods B ){
	return A.price<B.price;
}

bool weight(Goods A,Goods B){
	return A.weight<B.weight;
}
int MAX(int a,int b){
	if(a>=b) return a;
	else return b;
}

bool CP(Goods A,Goods B)
{
	return (A.price/A.weight)<(B.price/B.weight);
}
int funs1(int Capacity,Goods A[],int n)
{
	int Totalprice=0;
	sort(A,A+n,price);
	while(Capacity>0){
		if(A[n].weight<Capacity)
			Totalprice=Totalprice+A[n].price,
			Capacity=Capacity-A[n].weight,
			n--;
		else n--;

	}
	return Totalprice;
}
int funs2(int Capacity,Goods A[],int n)
{
	int Totalprice=0,i=0;
	sort(A,A+n,weight);
	while(Capacity>0)
	{
		if(A[i].weight<Capacity)
			Totalprice=Totalprice+A[i].price,
			Capacity=Capacity-A[i].weight,
			i++;
		else i++;

}
	return Totalprice;

}
int funs3(int Capacity,Goods A[],int n){
	int Totalprice=0,i=0;
	sort(A,A+n,CP);
	while(Capacity>0){
		if(A[n].weight<Capacity)
			Totalprice=Totalprice+A[n].price,
			Capacity=Capacity-A[n].weight,
			n--;
		else n--;

}
	return Totalprice;
}
int funs4(int Capacity,Goods A[],int n){
	int Totalprice=0;
	int i=1000,j;
	while(i>0){
		while(Capacity>0){
			j=(rand()%(n+1));
			if(Capacity>A[j].weight)
				Totalprice=A[j].price+Totalprice,
				Capacity=Capacity-A[j].weight,
				i--;
				else i--;
	}
	}
	return Totalprice;
}
int main()
{
	int Capacity;//背包容量
	int n;//物品数量
	cin>>Capacity>>n;
	Goods A[1000];
	for(int i=0;i<n;i++)
		cin>>A[i].price>>A[i].weight;
	cout<<MAX(funs3(Capacity,A,n),MAX(funs4(Capacity,A,n),MAX(funs1(Capacity,A,n),funs2(Capacity,A,n))));
}