【备战蓝桥杯】----01背包问题（动态规划）

?作者:云小逸
?个人主页:云小逸的主页
?Github:云小逸的Github
?motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==?
?专栏：C++? ?专栏：Java语言??专栏：Linux学习?
?专栏：C语言初阶??专栏：数据结构??专栏：备战蓝桥杯?

前言

今天我们来学习一下一个经典Dp问题----背包问题，这里将详细介绍背包问题的二维解法和一维解法。码字不易，请多多支持。

——————————————————————————————

0-1背包问题

背包问题是一个经典的动态规划问题，其基本形式是：有一个容量为 $V$ 的背包和 $n$ 个物品，每个物品有一个体积 $v_i$ 和一个价值 $w_i$。要求选择若干物品装入背包，使得装入背包中物品的总价值最大。其中每个物品只能选择装入一次。

二维解法

状态定义

设 $f(i,j)$ 表示前 $i$ 个物品，体积不超过 $j$ 的情况下可以获得的最大价值。

状态转移方程

对于第 $i$ 个物品，有两种选择：

1. 不放入背包，此时背包的最大价值为 $f(i-1,j)$；
2. 放入背包，此时背包的最大价值为 $f(i-1,j-v_i)+w_i$。

因此，状态转移方程为：

f ( i , j ) = max ⁡ { f ( i − 1 , j ) , f ( i − 1 , j − v i ) + w i } f(i,j)=\max\{f(i-1,j),f(i-1,j-v_i)+w_i\} f(i,j)=max{f(i−1,j),f(i−1,j−vi​)+wi​}

详细讲解：

f数组：

在背包问题中，f数组一般表示状态转移方程中的“状态”，即$f(i,j)$表示在前$i$个物品中，背包容量为$j$时的最大价值。也就是说，$f(i,j)$表示在当前背包容量为$j$的情况下，前$i$个物品能够获得的最大价值。在动态规划中，我们需要通过状态转移方程来不断更新$f(i,j)$的值，最终得到背包问题的最优解。

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);

这条语句是背包问题中的状态转移方程，表示在背包容量为 j 时，前 i 个物品能够获得的最大价值。

具体来说，f[i][j] 表示前 i 个物品，在背包容量为 j 时能够获得的最大价值。而根据背包问题的定义，第 i 个物品有两种选择，要么不装入背包，此时最大价值为 f[i-1][j]；要么装入背包，此时最大价值为 f[i-1][j-v[i]] + w[i]，其中 f[i-1][j-v[i]] 表示背包容量为 j-v[i] 时前 i-1 个物品的最大价值，w[i] 表示第 i 个物品的价值。因此，f[i][j] 就是这两种选择中的最大值。

代码实现

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 存储物品体积
int w[MAXN];    // 存储物品价值
int f[MAXN][MAXN];  // 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个物品的最大价值
            f[i][j] = f[i - 1][j];

            // 当前背包容量能够装下第i个物品，需要对是否选择第i个物品进行决策
            if(j >= v[i])   
                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)$ 表示体积不超过 $j$ 的情况下可以获得的最大价值。

状态转移方程

对于第 $i$ 个物品，有两种选择：

1. 不放入背包，此时背包的最大价值为 $f(j)$；
2. 放入背包，此时背包的最大价值为 $f(j-v_i)+w_i$。

因此，状态转移方程为：

f ( j ) = max ⁡ { f ( j ) , f ( j − v i ) + w i } f(j)=\max\{f(j),f(j-v_i)+w_i\} f(j)=max{f(j),f(j−vi​)+wi​}

详细解释：

int j = m; j >= v[i]; j–

这里的意思是从大到小枚举体积，因为在计算当前物品的最大价值时，需要用到之前物品的最大价值，而之前物品的最大价值可能已经被更新过，所以需要从大到小枚举体积，保证当前物品的体积不会影响之前物品的最大价值。同时，体积从大到小枚举也可以保证每个物品只被考虑一次，避免重复计算。

f[j] = max(f[j], f[j - v[i]] + w[i]);

在背包问题中，f[j]表示体积不超过j的情况下可以获得的最大价值。而f[j]的计算需要考虑两种情况：

1. 不选第i个物品，此时f[j]的价值为f[j]，即前i-1个物品的最大价值。
2. 选第i个物品，此时f[j]的价值为f[j - v[i]] + w[i]，即前i-1个物品在剩余容量为j - v[i]的情况下的最大价值加上第i个物品的价值w[i]。

因此，f[j]的值应该为这两种情况的最大值，即f[j] = max(f[j], f[j - v[i]] + w[i])。

代码实现

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 物品体积
int w[MAXN];    // 物品价值 
int f[MAXN];    // f[j]表示体积不超过j的情况下可以获得的最大价值

int main() 
{
    int n, m;   
    cin >> n >> m;  // n表示物品个数，m表示背包容量

    // 输入每个物品的体积和价值
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    // 01背包一维解法
    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;
}

总结

二维解法和一维解法都是经典的背包问题解法，二者的时间复杂度都是 $O(nm)$，但是一维解法的空间复杂度为 $O(m)$，比二维解法的 $O(nm)$ 更优秀。因此，在实际应用中，一维解法更为常用
​

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：

1. 短期拼智力、中期拼毅力、长期拼体力。不要觉得自己落后了，用马拉松的心态，过自己的一生，你慢了一时一分，别焦虑。要看你我是否七八十岁，还有扛着锄头上山种橙子的那种勇气。

2.人间的美好，是3月的风，6月的雨，9月的云和12月的雪。

3.痛苦是对的。 痛苦源于对现状的不满，只有不满足于现状的人才会痛苦，痛苦才会深刻。痛苦的人，才有欲望去改造这一切。焦虑也是对的。焦虑是因为你想做得更好，说明你追求高，说明你眼界高，说明你知识多。痛苦和焦虑的人才是最真实的你我。

4.人生没有办法做到始终一帆风顺，也没有办法万事如意。但凡是你渴望的，都是你拿不到的；但凡是你乞求的，都是你实现不了的。 年轻人才会悔恨过去，能够坦然接受这一切的都是智者。

5.人生有一段路，一定要自己去走。 黎明前那一段天是最黑的， 但是只要再熬那么一会儿，天就亮了。 耐心就是智慧。 就连太阳光到达地球需要八分钟，你急什么呢？ 那可是宇宙第一速度 。

​

最后如果觉得我写的还不错，请不要忘记点赞✌，收藏✌，加关注✌哦(｡･ω･｡)

愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油，为自己点赞！
​文章来源地址https://uudwc.com/A/xJqm

​