AcWing_2 01背包问题(模板)

09 Mar 2024 1311字 5分

AcWing

2. 01背包问题

01背包问题。定义二维状态数组f[i][j]表示考虑前i个物品，背包容量为j时，所有方案中的最大价值。

可以将f[i][j]分为以下两个集合：

背包容量为j时，选择装下物品i；
背包容量为j时，选择不装下物品i；

保证将f[i][j]分为这些集合之后不重不漏。则对于普遍的f[i][j]，其值即为这两种方案中价值最大的那个。

如果背包容量为j时，选择装下物品i，那么此时背包已经具有的物品，其容量最大为j-v[i]，这时的价值为前i-1个物品，容量j-v[i]中的价值与物品i的价值之和，f[i-1][j-v[i]] + w[i]；
如果背包容量为j时，选择不装下物品i，那么此时价值等同于f[i-1][j]。特殊地，如果背包的容量j本来就不足以装下物品i，那么f[i][j] = f[i-1][j].

所以，有：

当j >= v[i]时，f[i][j] = max{f[i-1][j-v[i]] + w[i], f[i-1][j]}；
当j < v[i]时，f[i][j] = f[i-1][j].

考虑边界条件，f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, ...，即当不取任何一个物品时，总价值一定为0.

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1010;
int v[N];    // 体积
int w[N];    // 价值 
int f[N][M];  // f[i][j], j容量下前i个物品的最大价值 
int main() {
    int n, m;   
    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 = 1; j <= m; j++){
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           
    cout << f[n][m] << endl;
    return 0;
}

考虑优化空间，使用一维数组，外层循环依次枚举物品种类，内层循环必须从大到小枚举背包容量，这样f[j]、f[j-v[i]]取得的都是上一个物品时的值。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1010;
int v[N], w[N];
int n, m;
int f[M];
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] << endl;
    return 0;
}