P1048 采药（01背包）

P1048 采药

法一：未优化空间，时间、空间复杂度均为O(NM)

#include<iostream>

using namespace std;

const int N = 1010;

/*
状态表示：f[i][j]表示取前i个草药，时间为j的最大价值 

状态转移：
        时间不够用 
        if(j < v[i]) f[i][j] = f[i - 1][j];
        else 
        时间够用
        f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]; 
*/

int m,n;
int w[N],v[N];
int f[N][N];
int res;

int main() {
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> v[i] >> w[i];
    }
    f[0][0] = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            if(j < v[i]){
                f[i][j] = f[i - 1][j];
            }else{
                f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= m; i ++ ){
        res = max(res,f[n][i]);
    }
    cout<<res<<endl;                         
    return 0;
}

优化后，时间复杂度不变，空间复杂度为O(M)

#include<iostream>

using namespace std;

const int N = 1010;

/*
状态表示：f[i][j]表示取前i个草药，时间为j的最大价值 

状态转移：
        时间不够用 
        if(j < v[i]) f[i][j] = f[i - 1][j];
        else 
        时间够用
        f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]; 
*/

int m,n;
int w[N],v[N];
int f[N][N];
int res;

int main() {
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> v[i] >> w[i];
    }
    f[0][0] = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            if(j < v[i]){
                f[i][j] = f[i - 1][j];
            }else{
                f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= m; i ++ ){
        res = max(res,f[n][i]);
    }
    cout<<res<<endl;                         
    return 0;
}