C++

二维数组f[m][n]表示最优解

假设背包容量在j下的前m-1个物品的最优解以得出，那么只需考虑是否选择最后一个，默认情况是不选择，当最后一个物品的体积 <= 背包剩余容量，则可以选择最后一个物品（映射if选择）

#include<iostream>

using namespace std;

const int N = 1010;

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

int main(){
    //录入数据
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    //计算,体积v[],价值w[]
    //思想：前i个物品，背包容量为j下的最大值
    for( int i = 1;i <= n ;i++ ){
        for( int j = 1; j <=m ;j++){
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
        }
    }
    cout << f[n][m];
    return 0;
}

时间复杂度 $O(m*n)$(暴力枚举)

最优解一定是计算的二维数组最后一个值，即f[m][n]，前面f[m-1][]个都是为计算最后的选手在做铺垫

是否选择最后一个物品：最后一个物品体积 <= 背包剩余容量

一维数组f[m]表示最优解(优化解法)

#include<iostream>

using namespace std;

const int N = 1010;

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

int main(){
    cin >> n >> m;                                                                                                                                                                          
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n ;i++){
        for(int j = m ;j >= v[i]; j--){
            f[j] = max(f[j],f[j-v[i]] + w[i]);
        }
    }

    cout << f[m];
    return 0;
}

时间复杂度 $O(m*n)$

原理与二维数组相同，空间复杂度由$O(n^2)$降至$O(n)$