动态规划:01背包问题

---

---

前言

动态规划主要运用状态转移方程(即递推方程)解决步骤问题,一般来说遍历方向有从前到后和从后到前,具体问题具体分析
下面具体讲解一下动态规划的01背包问题:
(一般来说,01背包问题不会刻意出题,但是会解决有限的容量中得到利益最大的一类问题)

一、什么是动态规划

动态规划（Dynamic Programming, DP）
动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它通常用于求解最优化问题。动态规划通过存储已解决的子问题的答案，来避免重复计算，这是其提高效率的关键。它要求问题必须满足两个主要条件：

最优子结构：问题的最优解包含其子问题的最优解。即，可以通过组合子问题的最优解来得到原问题的最优解。
重叠子问题：在求解过程中，多个子问题被反复求解。通过存储这些子问题的解，可以避免重复计算。

二、动态规划与贪心法的区别

解决问题类型：
动态规划主要用于解决最优化问题，特别是那些具有重叠子问题和最优子结构的问题。
贪心算法主要用于解决具有贪心选择性质的问题，即每一步选择都看起来是最优的，且希望通过这些局部最优解来达到全局最优解。
策略与结果：
动态规划通常是通过构建一个状态转移方程，然后自底向上或自顶向下逐步求解。它通过保存已求解的子问题的解来避免重复计算，确保能得到全局最优解。
贪心算法则是通过贪心选择策略，直接做出当前看来最优的选择，但不保证这些选择能够组成全局最优解。
适用范围：
动态规划适用于问题规模较大，但状态转移方程较简单的情况。它提供了一种系统性的方法来解决复杂问题。
贪心算法则适用于问题本身具有贪心选择性质的情况，通常更加直观和易于实现，但不一定能得到全局最优解。

三、动态规划解决01背包问题实例

1.01背包问题描述

有n件物品和一个最多能背的重量有限的背包,第i件物品的重量是weigh[i],得到的价值是value[i],每件物品只能用1次,求解将哪些物品装入背包里物品价值总和最大

2.图例

物品编号	重量	价值
0	1	15
1	3	20
2	4	40

3.动规五部曲

(PS:新手小白喜欢跟着卡尔(代码随想录)一个超级牛的大佬学习的)总结的很有思路 超ai~
1.明确dp数组的含义: 本题中为什么会想到二维数组dp[i][j]来表示呢,因为需要一个i来存储重量,一个j来存储背包容量,这样在二维数组表示中就不需要那么多的冗余for循环来设置变量了
dp[i][j]:表示下标0~i之间的物品任取,放进容量为j的背包中,dp[i][j]表示最大的总价值.
2.确定状态转移方程(最难点)
我们会想:dp[i][j]是由哪个状态推导而来呢,仔细琢磨一下是不是又i的状态而来
两种状态
1----dp[i-1][j]: **i不放入背包:**不放入背包时容量j自然不会变化,即背包的剩余容量小于i的重量,无法放入,那么此时,需要if语句判断一下重量的大小比较
2----dp[i-1][j-weight[i]]:i放入背包:这个比较难理解在于为什么放入背包之间的最大价值中是第二个坐标是j-weight[i]呢
我们不妨换个角度理解:
当i放进去时，那么这时候整个物品集就被分成两部分，下标0到i-1和下标为i，而这是i是确定要放进去的，那么就把j空间里的weight[i]给占据了，只剩下j－weight[i]的空间给前面i－1，那么只要这时候前面i－1在j－weight[i]空间里构造出最大价值，即dp【i－1】【j－weight[i]】，再加上此时放入的i的价值value[i]，就是dp[i][j]了!!!
那么此时只需要取两者之间的最大值即可

//状态转移方程
for(int i=1;i<weight.size();i++){
	for(j=0;j<=bagweigt;j++){
		dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
	}
}
复制

3.初始化dp数组
思考一下状态转移方程,是不是对于一个一般的i,j只需要知道它的正上方(即i-1,j)和左上方(即i-1,j-weight[i])就可推导而来

vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));  
      
    // 初始化第一列  
    for (int j = weight[0]; j <= bagweight; j++) {  
        dp[0][j] = (j >= weight[0]) ? value[0] : 0;   
    }  
复制

4.遍历顺序
由状态转移方程:一定是从左到右,从上到下遍历
5.打印dp数组以防出错

4.完整代码

#include <bits/stdc++.h>  //万能头文件
using namespace std;  
  
void test01bag(){  
    vector<int> weight = {1, 3, 4};  //初始化weight数组
    vector<int> value = {15, 20, 30};  //初始化value数组
    int bagweight = 4;  //背包容量
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));  //vector二维数组的定义,一开始全部初始化为0,由代码可知,此二维数组是3行5列,可以画一下加深理解
      
    // 初始化第一行  
    for (int j = weight[0]; j <= bagweight; j++) {  
        dp[0][j] = (j >= weight[0]) ? value[0] : 0;   //三目运算符
    }  
      
    for (int i = 1; i < weight.size(); i++) { // 从第二个物品开始遍历  
        for (int j = 0; j <= bagweight; j++) {  
            if (j < weight[i])  
                dp[i][j] = dp[i - 1][j];  
            else  
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);  
        }  
    }  
      
    cout << dp[weight.size() - 1][bagweight] << endl; // 输出最大价值  
}  
  
int main() {  
    test01bag(); // 直接调用函数  
    return 0;  
}
复制

总结

例如：以上就是今天要讲的内容，本文仅仅简单介绍了动态规划中最经典的01背包问题,下期讲解最长递增子序列和最长连续递增子序列,大家好好理解一下哦