01背包问题通俗易懂解法

逃离我推掉我的手 2023-02-23 08:54 8阅读 0赞

## 一、前言 ##

动态规划经典问题，01背包问题记录。

## 二、问题描述 ##

假设有 n 件物品，至多可装入容积为 m 的容器当中，试问最大可装入的价值为多少？设w\[ i \]为第 i 件物品重量，v\[ i \]为第i件物品价值dp\[ i \]\[ j \]表示将前i件物品装入重量 j 的容器当中。

## 三、动态规划解题思路 ##

### 3.1 先回顾一下动态规划算法设计步骤 ###

1.  刻画一个最优解的结构特征。
2.  递归地定义最优解的值。
3.  计算最优解的值，通常采用自底向上的方法。
4.  利用计算出的信息构造一个最优解。

步骤1~3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤4。如果确实要做步骤4，有时就需要在执行步骤3的过程中维护一些额外信息，以便用来构造一个最优解。

这里我们用自底向上的方法。

### **3.2 自底向上解决方法** ###

自底向上顾名思义就是条件由少到多计算结果，前面计算的结果用于后面计算。以这道题为例：

w = \{2,1,3,2\}

v = \{12,10,20,15\}

m = 5

求可装最大价值是多少？

**3.2.1 问题图解**

![20200706222243729.png][]

1）物品数量为空，容量为1-5的容器存放的价值都是0

![20200706222250279.png][]

2）只有第一件物品：w=2，v=12，容器体积大于等于2的都可以放入第一件物品价值为12

![20200706222325617.png][]

3）加入第二件物品：w=1，v=10，容积是1的容器可以装入价值是10的物品；容积是2的容器可以装入价值是12的物品；容积大于等于3的容器可以装入价值是22（12+10）的物品

![20200706222407871.png][]

4）加入第三件物品：w=3，v=20，容积是1的容器可以装入价值是10的物品；容积是2的容器可以装入价值是12的物品；容积3的容器可以装入价值是22（12+10）的物品；容积4的容器可以装入价值是30（20+10）的物品；容积5的容器可以装入价值是32（12+20）的物品

![20200706222438646.png][]

5）加入第四件物品：w=2，v=15，容积是1的容器可以装入价值是10的物品；容积是2的容器可以装入价值是15的物品；容积3的容器可以装入价值是25（10+15）的物品；容积4的容器可以装入价值是30（20+10）的物品；容积5的容器可以装入价值是32（12+10+15）的物品

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

最终的结果是37。

**3.2.2 递推公式**

![20200706222535933.png][]

上面图，通过递推公式来说明这个求解过程，以加入第四件物品容积为5为例，它是在两个价值中取最大价值，价值一：没有加入第四件物品，容积为5最大价值是32，之前已经求解；价值二：包含第四件物品，在剩余容积中选择最大价值的物品，剩余容积是3，容积3最大价值是22，最大价值是37（22+15）；最终最大价值是37。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

## 四、总结 ##

如果一个问题可以拆分成多个小问题，而最终结果又依赖拆分后的小结果，可以考虑用动态规划来解决。动态规划需要先找到递推公式，利用计算出的信息构造一个最优解。

## 五、编码实现 ##

//==========================================================================
    /**
    * @file    : Knapsack.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107169498
    * @author  : niebingyu
    * @date    ：2020/07/05
    * @title   : 01背包问题
    * @purpose : 假设有 n 件物品，至多可装入容积为 m 的容器当中，试问最大可装入的价值为多少？
    *			 设w[ i ]为第 i 件物品重量，v[ i ]为第i件物品价值
    *			 dp[ i ][ j ]表示将前i件物品装入重量 j 的容器当中
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <list>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_KNAPSACK namespace NAME_KNAPSACK {
    #define NAMESPACE_KNAPSACKEND }
    NAMESPACE_KNAPSACK
    class Solution
    {
    public:
        int knapsack(vector<int>& w, vector<int>& v, int n, int weight)
        {
            if (w.size()-1 != n || v.size()-1 != n)
                return {};
            
            vector<vector<int>> dp(n +1, vector<int>(weight+1, 0));
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= weight; j++)
                {
                    if (i == 0 || j == 0) 
                        dp[i][j] = 0;   //边界dp，结果为0 
                    else 
                    {
                        if (j < w[i]) 
                            dp[i][j] = dp[i - 1][j];//装不下 
                        else 
                            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);//装得下，max比较装或不装哪个更大 
                    }
                }
            }
    
            return dp[n][weight];
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& w, vector<int>& v, int num, int weight, int expect)
    {
        Solution s;
        int result = s.knapsack(w, v, num, weight);
        if (expect == result)
        {
            cout << testName << ", solution passed." << endl;
        }
        else
        {
            cout << testName << ", solution failed." << endl;
        }
    }
    
    void Test1()
    {
        vector<int>w = { 0,2,1,3,2 };
        vector<int>v = { 0,12,10,20,15 };
        int num = w.size()-1;
        int weight = 5;
    
        int expect = 37;
    
        test("Test1()", w, v, num, weight, expect);
    }
    NAMESPACE_KNAPSACKEND
    // 测试 用例 END
    //
    
    void Knapsack_Test()
    {
        NAME_KNAPSACK::Test1();
    }

**执行结果：**

![20200706222855339.png][]

[20200706222243729.png]: https://img-blog.csdnimg.cn/20200706222243729.png
[20200706222250279.png]: https://img-blog.csdnimg.cn/20200706222250279.png
[20200706222325617.png]: https://img-blog.csdnimg.cn/20200706222325617.png
[20200706222407871.png]: https://img-blog.csdnimg.cn/20200706222407871.png
[20200706222438646.png]: https://img-blog.csdnimg.cn/20200706222438646.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200706222501714.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200706222535933.png]: https://img-blog.csdnimg.cn/20200706222535933.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020070622274544.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200706222855339.png]: https://img-blog.csdnimg.cn/20200706222855339.png