01背包问题

原题链接

题目描述

有 $n$ 件物品和一个容量是 $m$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $w_i$，价值是$v_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过且总价值最大。

输出最大价值。

分析

01背包问题属于动态规划问题中的背包问题中的一种经典题目，其物品的个数仅有 $1$ 个。

一般的动态规划问题的有以下的几个步骤。

确定状态

首先使用二维数组表示状态。

我们从问题入手，定义 $f_{i, j}$ 为前 $i$ 件物品，在背包容量为 $j$ 的情况下所装物品的最大价值和。

划分阶段

按照从上往下，从左往右的顺序求解，即按照 $f_{1, 1},f_{1, 2},\dots,f_{1, m},\ f_{2, 1},f_{2, 2},\dots,f_{2, m},\ \dots \ f_{n, 1},f_{n, 2},\dots,f_{n, m}\ $ 的顺序求解。

决策选择

如果要求解 $f_{i, j}$，那么对于所有的第 $i$ 件物品，都可以选或不选。这里做分类讨论。

如果不选第 $i$ 件物品

如果不选第 $i$ 件物品，相当于从前 $i-1$ 件物品中选择，并且背包容量仍然为 $j$。那么此时的 $f_{i, j} = f_{i-1, j}$。

如果选第 $i$ 件物品

如果选第 $i$ 件物品，首先需要判断当前的背包容量是否允许装入这一件物品，即如果 $w_i > j$，就代表不能放进，也就不做讨论了。

如果可以放下，就需要讨论放下它会带来的影响。首先这件物品将占据 $w_i$ 的空间，但同时也会增加 $v_i$ 的价值。也就是说要在前 $i-1$ 件物品中选择一些物品，但这些物品的总体积加上第 $i$ 件物品的总体积不能超过 $j$。换言之，必须要在前 $i-1$ 件物品中找到在背包容量不超过 $j-w_i$ 的情况下的最大价值，然后加上 $v_i$。

整理一下，如果能放下这件物品，那么 $f_{i, j} = f{i-1, j-w_i} + v_i$。

取最大值

在选或不选第 $i$ 件物品所能提供的价值中选择较大值，为 $f_{i, j}$ 赋值。

因此，动态转移方程即：

\[f_{i, j} = \left\{\begin{matrix}f_{i-1, j} & (w_i > j)\\ \max(f_{i-1, j}, f_{i-1, j-w_i} + v_i & (w_i \le j) \end{matrix}\right. \]

边界条件

如果一件物品也不选，那么价值也就是 $0$，所以所有的 $f_{0, i}$ 都是 $0$。

如果背包容量为 $0$，那么一件物品也放不下，价值也就是 $0$，所以所有的 $f_{i, 0}$ 都是 $0$。

求解目标

由于 $f_{i, j}$ 为前 $i$ 件物品，在背包容量为 $j$ 的情况下所装物品的最大价值和，那么前 $n$ 件物品，在背包容量为 $m$ 的情况下所装物品的最大价值和即为 $f_{n, m}$。

代码

#include <iostream>

using namespace std;

const int N = 40, M = 210;

int n, m;       // n 件物品，背包容量为 m
int w[N];       // w[i] 表示第 i 件物品的重量
int v[N];       // v[i] 表示第 i 件物品的价值
int f[N][M];    // f[i][j] 表示前 i 件物品，背包容量为 j 的情况下，所能提供的最大价值和

int main(){
    // 读入
    scanf("%d%d", &m, &n);
    
    for(int i=1; i<=n; i++){
        scanf("%d %d", w+i, v+i);
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(w[i] > j){   // 如果不能放下第 i 件物品
                f[i][j] = f[i-1][j];
            }
            else{           // 如果不能放下第 i 件物品
                f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
            }
        }
    }
    
    // 输出答案
    printf("%d\n", f[n][m]);
    
    return 0;
}

优化

在上述代码中，空间复杂度为 $\Theta(n \cdot m)$。

如果仔细观察，不难发现，每一次求解 $f_{i,j}$ 时都只会和上一列的数值有关。

因此可以将二维数组变成一维数组，存储的是上一行的数值，更改时可以忽略掉 $i-1$ 的操作。

但是求解 $f_{i, j}$ 时有可能会从上一行的前面转移而来，所以如果换成一位后先修改前面的数值会影响到后面的结果，因此需要从后向前推导。

综上所述，动态转移方程就应变为：

\[f_{j} = \max(f_{j},\ f_{j-w_i} + v_i) \]

最终结果为 $f_m$。

#include <iostream>

using namespace std;

const int N = 40, M = 210;

int n, m;       // n 件物品，背包容量为 m
int w[N];       // w[i] 表示第 i 件物品的重量
int v[N];       // v[i] 表示第 i 件物品的价值
int f[M];    	// 一维优化 

int main(){
    // 读入
    scanf("%d%d", &m, &n);
    
    for(int i=1; i<=n; i++){
        scanf("%d %d", w+i, v+i);
    }
    
    for(int i=1; i<=n; i++){
        for(int j=m; j>=w[i]; j--){		// 倒序求解 
            f[j] = max(f[j], f[j-w[i]] + v[i]);
        }
    }
    
    // 输出答案
    printf("%d\n", f[m]);
    
    return 0;
}

JZTXT

01 背包