一维背包

2008-10-02 11:38


#include<iostream>
using namespace std;
int main(void){
    int f[30000];
    int n,m,v[30],p[30];
    int i,j;
    memset(f,0,sizeof(f));
   
    cin>>n>>m;
    for(i=1;i<=m;i++)
        cin>>v[i]>>p[i];
    for(i=1;i<=m;i++)
        for(j=n-v[i];j>=0;j--)
            if((f[j]+v[i]*p[i])>f[j+v[i]])
               f[j+v[i]] = f[j]+v[i]*p[i];
   
    cout<<f[n]<<endl;
    system("pause");
   
    return 0;
}