#include#include #include using namespace std;int result[1001][101];int w[101],v[101];int main(){ int totalTime , count; memset(result , 0 ,sizeof(result)); scanf("%d %d" , &totalTime , &count); for ( int i = 1 ;i <= count ; i++) scanf("%d %d" , &w[i] , &v[i]); for ( int i = 1 ; i <= totalTime ; i++) for (int j = 1 ; j <= count ; j++) { if ( i - w[j] >= 0 ) result[i][j] = max(result[i][j-1] , result[ i - w[j]][j-1]+v[j]) ; else result[i][j] = result[ i ][ j -1]; } printf("%d\n" ,result[totalTime][count]); return 0 ;}
posted on 2012-03-20 00:05 阅读( ...) 评论( ...)