背包问题

背包问题

13 155 102 83 9样例输出
65
#include <bits/stdc++.h>using namespace std;const int maxn = 105;struct res{	int v,w;}arr[maxn];int s,m;bool cmp(res x,res y){	 return x.v>y.v;//按物品单位重量的价值从大到小排序}int main(){	int n,sum,m;	cin>>n>>m;	for(int i=0;i<n;i++)	{	    cin>>arr[i].w>>arr[i].v;	}		sort(arr,arr+n,cmp);		sum=0;		for( int i=0;i<n;i++)		{			if(m-arr[i].w>0)		//能取完全部都取			{				sum+=arr[i].v*arr[i].w;				m-=arr[i].w;			}			else					//不能取完，取一部分			{				sum+=m*arr[i].v;				break;			}		}		cout<<sum<<endl;	return 0;}