背包问题

1
3 15
5 10
2 8
3 9

样例输出

65

#include<iostream>
using namespace std;
int main()
{
	int n,s,m,v[11],w[11],sum,t,i,j;//v[11]表示价值，w[11]表示重量
	cin>>n;
	while(n--)
	{
		sum=0;
		t=0;
		cin>>s>>m;
		for(i=0;i<s;i++)
			cin>>v[i]>>w[i];
		for(i=0;i<s;i++)
		{
			for(j=0;j<s-1-i;j++)
			{
				if(v[j+1]>v[j])//按物品的价值从大到小的排序
				{
					swap(v[j],v[j+1]);
					swap(w[j],w[j+1]);
				}
			}
		}
		for(i=0;i<s;i++)
		{
			sum+=w[i];
			if(sum>m)
				break;
		}
		if(i==0)
			cout<<m*v[0]<<endl;
		else
		{
			for(j=0;j<i;j++)
			{
				t+=v[j]*w[j];
				m-=w[j];
			}
			cout<<t+m*v[i]<<endl;
		}
	}
	return 0;
}