动态规划01背包问题手画图解

        经典dp动规问题，01背包问题关键在于遍历顺序与初始化这两步的推导。

目录

文章目录

一、01背包问题

二、确定dp数组及其下标含义

三、确定递推公式

四、确定初始化

 五、确定遍历顺序

六、举例推导dp数组

总结

---

 

一、01背包问题

        有n件物品，每件的价值与重量限制了背包所能装的总价值，每件物品只有一个，求所能装的最大价值。

二、确定dp数组及其下标含义

        dp[i][j]代表的是：

        从0-i的物品中选，放入容量为j的背包中所得的最大价值。

三、确定递推公式

        现态dp[i][j]有两种情况：容量j够放物品 容量j不够放物品 。

        显而易见的是：

        ①当不够放物品时，背包中的价值并不会增加，仍然停留在拿取上一个物品（i-1）的总价值（dp[i-1][j] 0）上； 

        ②当还能放得下物品时，就需要判断放了这个物品和不放这两种情况谁获得的最终价值更大；

                1.放第i件物品价值大时：需要在容量（j - weight[i]）上减去所放进去的第i件物品的重量，价值（上一件物品留下的价值：dp[i-1][j]）上加上第i件物品的价值（dp[i-1][j] value[i]）。

                        第1点综合起来便是：dp[i-1][j - weight[i]] value[i];

                2.不放第i件物品价值大时：与①的情况相同，都是没有将第i件物品放进去。

                                第2点便是：dp[i][j] = dp[i-1][j];

图解如下图： 

---

四、确定初始化

        由递推公式可知：每一行（i）的数据都是由上一行（[i-1][j]或者[i-1][j-weight[i]]）得到的，也即：每一元素数据的来源是上方或者是左上方，所以我们需要得到最上方一行的初始化数据与最左边一行的数据。

         题外话：当然，这是从科学的角度进行的思考，如果不这么严谨的话，我们至少可以得到：当容量为0时，所获总价值一定为0（背包放不下东西）。

        首先从背包容量进行考虑：

        ①当容量为0时，所获总价值一定为0（背包放不下东西）；

        ②当容量能够放得下物品[0,0]（j >= weight[0] = 1）时，可以得到的最大价值就是value[0]（15）；

图解如下：

 五、确定遍历顺序

        由递推公式可知：

        我们需要得到上一行的数据即可进行递推。

        ①从左到右，从上到下；②或者从上到下， 然后从左到右；两种遍历顺序都可以得到所求数据上一行的所有数据，都可以进行递推。

图解如下： 

六、举例推导dp数组

图解如下：  

        

七、代码实现

1.  
   #include <iostream>
2.  
   #include <vector>
3.  
   using namespace std;
4.  
    
5.  
   void BagSolution()
6.  
   {
7.  
   vector <int>value = { 15,20,30 };
8.  
   vector <int>weight = { 1,3,4 };
9.  
   int bagWeight = 4;
10.  
    // 列多出来容量为0的那列
11.  
    vector <vector<int>> dp(weight.size(), vector <int>(bagWeight 1, 0));
12.  
    // 初始化--容量为0所能放的价值一定为0
13.  
    for (int i = 0; i < weight.size(); i )
14.  
    {
15.  
    dp[i][0] = 0;
16.  
    }
17.  
    // 当容量能放下下标为0物品（最小重量）时，最大价值就是value[0]
18.  
    for (int j = 0; j <= bagWeight; j )
19.  
    {
20.  
    if (j >= weight[0])
21.  
    {
22.  
    dp[0][j] = value[0];
23.  
    }
24.  
    }
25.  
    //确定遍历顺序
26.  
    for (int i = 1; i < weight.size(); i )
27.  
    {
28.  
    for (int j = 1; j <= bagWeight; j )
29.  
    {
30.  
    // 容量不够放,第i件物品就不放
31.  
    if (j < weight[i])
32.  
    {
33.  
    dp[i][j] = dp[i - 1][j];
34.  
    }
35.  
    // 够放->比较拿了大还是不拿大
36.  
    else
37.  
    {
38.  
    dp[i][j] = max(dp[i-1][j], dp[i - 1][j - weight[i]] value[i]);
39.  
    }
40.  
    }
41.  
    }
42.  
    // 打印dp
43.  
    for (int i = 0; i < weight.size(); i )
44.  
    {
45.  
    for (int j = 0; j <= bagWeight; j )
46.  
    {
47.  
    printf("- ", dp[i][j]);
48.  
    }
49.  
    cout << endl;
50.  
    }
51.  
    }
52.  
     
53.  
    int main()
54.  
    {
55.  
    BagSolution();
56.  
    return 0;
57.  
    }

运行截图：

总结

        01背包问题是所有背包问题的根本所在，掌握好dp五部曲，明确dp及其下标含义，勤加练习是制胜之道！

这篇好文章是转载于：学新通技术网