经典背包问题
#include<iostream> #include<cstdio> using namespace std; #define MAXN 100 + 10 #define MAXT 1000 + 10 int d[MAXN][MAXT]; int main() { int n, C,time,value; scanf("%d%d",&C,&n); for(int i = 1; i <= n ; ++i) { scanf("%d%d",&time,&value); for(int j = 0; j <= C; j++) { d[i][j] = (i==1 ? 0 : d[i-1][j]); if(j >= time) d[i][j] = d[i][j] >= d[i-1][j-time]+value? d[i][j]:d[i-1][j-time]+value; } } printf("%d\n", d[n][C]); //system ("pause"); return 0; }