开心的金明.cpp

背包类问题浅析和一些背包类问题的解答源程序。

#include <iostream>
using namespace std;

int main(){
    const int M = 30, N = 30009;
    int n, m, f[N]={0}, i, j, value, price;
    cin >>n >>m;
    for( i=0; i<m; ++i ){
         cin >>price >>value;
         value *= price;
         for( j=n; j>=price; --j )
              if( f[j-price] + value > f[j] ) f[j] = f[j-price] + value;
    }
    
    cout <<f[n] <<endl;
    system( "pause" );
    return 0;
}