Snake52996 2017-10-22 05:48:29
点我顶贴
收藏
删除
因为题目数据范围不大,可以直接动态规划,甚至不需要优化.
#include<iostream>
#include<cmath>
using namespace std;
const int MAX=30;
int v[MAX],p[MAX];
int n,m;
int dg(int i,int sum)
{
if(i>=m) return 0;
if(sum+v[i]>n) return dg(i+1,sum);
return max(dg(i+1,sum+v[i])+v[i]*p[i],dg(i+1,sum));
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++) cin>>v[i]>>p[i];
cout<<dg(0,0);
return 0;
}