大家看下,下面是一个十分普通的通用贪心解法,
为什么只有30分呢(本人没学过01背包)?
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
struct t{
int v,w;
}j[30];
bool cmp(t a,t b){
if(a.v*a.w!=b.v*b.w)return a.v*a.w>b.v*b.w;
return a.w>b.w;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>j[i].v>>j[i].w;
}
sort(j+1,j+m+1,cmp);
for(int i=1;i<=m;i++){
if(j[i].v<=n){
ans+=j[i].v*j[i].w;
n-=j[i].v;
}
if(n==0)break;
}
cout<<ans;
return 0;
}