AcWing 2. 01背包问题

附上优质博文

01背包问题详解

未优化，二维数组

#include <iostream>
using namespace std;
const int N = 1010;
int f[N][N]; //f(i,j) 放入第i件的集合中，不超过容量j的最大价值
int v[N],w[N];
int m,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 = 0; j <= m; j++){
            f[i][j] = f[i-1][j];//左半边的集合
            if(v[i]<=j)//当第i件的体积大于容量j时，才进行下一步比较，否则没有意义
                f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    cout << f[n][m];
    return 0;
}

y总分析思路（重点）

优化空间后（附带注释）

 #include <iostream>
using namespace std;

const int N = 1010;
int f[N]; //f[j]表示容量为j时，价值最大
int v[N],w[N];
int m,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 >= 0; j --){
            //f[j] = f[j];//为什么这里两个都是j？ 解答：此时f(j)表示当前容量为j时的最佳结果，与放不放第i件物品无关
            if(v[i]<=j)//当第i件的体积大于容量j时，才进行下一步，否则没有意义
                f[j] = max(f[j], f[j-v[i]] + w[i]);

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