这题可以说就是01背包的例题,我没什么多余的解释,上代码:
C语言:
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[30000];
int main(void)
{
int n, m;
int i, j;
int a, b;
scanf(%d%d, &n, &m);
for(i = 0; i < m; i++){
scanf(%d%d, &a, &b);
for(j = n; j >= a; j--){
f[j] = max(f[j], f[j - a] + a * b);
}
}
printf(%d\\n, f[n]);
return 0;
}