领略算法真谛：01背包问题

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记  闲言碎语小记坊 题山采玉

目录

01背包问题：

理论讲解

1.状态表示：

2.状态转移方程：

3.初始化

4.填表顺序

5.最终结果

3.1.1 (模板)01背包

思路讲解：

代码展示：

空间复杂度优化：

背包问题分为了很多类有01背包问题，完全背包问题，混合背包问题，多重背包问题，分组背包问题,多维费用背包问题。但所有的背包问题都是从01背包问题为基础展开优化的。所以让我们先来了解一下01背包问题吧！

01背包问题：

理论讲解

我们有一个体积为5的背包，而有n样物品他们有价值和所占的体积，每个物品只能选一次，要求最多能装进多少价值的物品，这道题我们有些人第一想法是贪心，但无论我们是按照v最小排序还是w最小排序或者是w/v排序都能举出反例，那我们还是得使用dp动态规划来解决这个问题。

1.状态表示：

我们可以使用一个二维数组来表示动态表示，f[ i ] [ j ] 表示我们从前 i 号物品中选体积不超过j的最大总价值。

2.状态转移方程：

我们如果对dp有一点经验的话一般我们会以最后一个状态来推导。比如到f [ i ][ j ]，我们有两种选择，一种是我们不选i号物品，那我们的最大价值在前一个状态，f[i - 1][ j ],而另一种是选择i号物品，但要保证i号物品的体积要小于总体积，然后我们找 j - v[i] 体积的状态，f[i - 1][j - v[i] ] + w[i];

3.初始化

我们当 j 等于0时，表示体积小于等于0也就是空背包，那最大价值肯定是0啊！当i等于0时，从前0号物品选体积小于等于j那也是0啊，所以我们要将f数组全初始化为0，放在全局即可。

4.填表顺序

由于我们要上一行的状态，那我们仅需从上向下填表，从左往右还是，从右往左都行。

5.最终结果

结果肯定是在f[n][m]上。

3.1.1 (模板)01背包

题目来源： 牛客网

题目链接：【模板】01背包

难度系数： ★★

每个物品只能选一次。

1. 求这个背包⾄多能装多⼤价值的物品？

2. 若背包恰好装满，求⾄多能装多大价值的物品？

这题的第一问，我们已经模拟过了，我们来看看第二问吧！

题目要求全装满

思路讲解：

1.状态表示：2.状态转移方程：这些我们可以在第一问上稍微修改一下，

即1：在f[ i ] [ j ] 表示我们从前 i 号物品中选体积等于j的最大总价值。

2：状态转移方程其实是一样的

那我们最关键的点就在初始化上了

3：初始化

我们当 j 等于0时，表示体积等于0时，从前i号选，那还是0，这个是没问题的，关键问题就出在i==0时，我们要从前0号物品选体积等于j的价值，我们没有物品怎么选到价值刚好等于j呢？所以当i ==0 的点是无效点，我们得将他初始化成一个不会影响后续的值，0会影响到，注意我们状态转移方程是取max，所以我们仅需将j ==0的地方初始化为负无穷，我们可以将f数组全部初始化为负无穷，因为，不只有i==0的点是无效的。

但我们还得关注一点，0，0点是有效的得初始化为0；

其他过程完全一样。

代码展示：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int n, m;
int main()
{
    //不超过 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 = 0; 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] << endl;
    //恰好等于m
    //初始化
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; 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]);                    
        }    
    }
    if(f[n][m] >= 0)
        cout << f[n][m] << endl;
    else 
        cout << 0 << endl;
    return 0;
}

我们关注到我们仅仅只使用了前一行的值，那我们可不可以创建两个数组来替代f的二维数组呢？

那是行的，我们还有一个思路，我们会使用该点的左边的值，那我们从右边遍历，然后覆盖数组，我们就能使用一个数组来优化空间复杂度了。

空间复杂度优化：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int n, m;
int main()
{
    //不超过 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 = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);                    
            
    cout << f[m] << endl;
    //恰好等于m
    //初始化
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    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]); 
            
    if(f[m] >= 0)
        cout << f[m] << endl;
    else 
        cout << 0 << endl;
    return 0;
}