• 背包问题（01背包，完全背包，多重背包，用二进制优化的多重背包，分组背包）

    来几张乐色的笔记，供自己以后方便复习：

     

     

     

     

     

     

     

     

    2. 01背包问题

    有 N

    件物品和一个容量是 V

    的背包。每件物品只能使用一次。

    第 i

    件物品的体积是 vi，价值是 wi

    。

    求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
    输出最大价值。

    输入格式

    第一行两个整数，N，V

    ，用空格隔开，分别表示物品数量和背包容积。

    接下来有 N

    行，每行两个整数 vi,wi，用空格隔开，分别表示第 i

    件物品的体积和价值。

    输出格式

    输出一个整数，表示最大价值。

    数据范围

    0


    0

    输入样例

    1. 4 5
    2. 1 2
    3. 2 4
    4. 3 4
    5. 4 5

    输出样例：

    8

    /**
     * 状态设计：dp[i][j] : 表示不超过前i件物品，且容量不超过j 的最大价值
     * 方案；
     * 状态转移方程：dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]] +c[i]);
     *
     * 由于每一次更新dp[i][j]的值都只用到了第一维的值，所以我们可以只要一个
     * 一位数组来存储，这个一维数组称为滚动数组；
     * 但是当j作为背包的容量时，j从小到大或者从大到小的选择不当时，状态
     * 转移方程就会发生错误；
     * 当需要用到滚动数组的时候，先求出状态转移方程的朴素方程，再将用滚动
     * 数组的状态转移方程转换朴素法，如果与朴素方法相同，则此用滚动数组优
     * 化的状态转移方程是为正确；
     *
     * 题目中的状态转移方程瞬息万变，应该掌握这种方法，理解这种思想，而
     * 不能去死记硬背；
    */

    第一个：二维数组进行状态设计：

    1. #include <iostream>
    2. #include <algorithm>
    3.  
    4. using namespace std;
    5.  
    6. const int maxn = 1010;
    7. int dp[maxn][maxn];
    8. int w[maxn],c[maxn];
    9.  
    10. int main()
    11. {
    12.     int n,v;
    13.     cin >> n >> v;
    14.     
    15.     for(int i=1;i<=n;++i)
    16.         cin >> w[i] >> c[i];
    17.     
    18.     for(int i=1;i<=n;++i)
    19.         for(int j=0;j<=v;++j)
    20.         {
    21.             if(j<w[i])
    22.                 dp[i][j] = dp[i-1][j];
    23.             else
    24.                 dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]]+c[i]);
    25.         }
    26.         
    27.     cout << dp[n][v] << endl;
    28.     return 0;
    29. }

    第二个：滚动数组优化

    1. #include <iostream>
    2. #include <algorithm>
    3.  
    4. using namespace std;
    5.  
    6. const int maxn = 1010;
    7. int dp[maxn];
    8. int w[maxn],c[maxn];
    9.  
    10. int main()
    11. {
    12.     int n,v;
    13.     cin >> n >> v;
    14.     
    15.     for(int i=1;i<=n;++i)
    16.         cin >> w[i] >> c[i];
    17.     
    18.     for(int i=1;i<=n;++i)
    19.         for(int j=v;j>=0;--j)
    20.         {
    21.             if(j<w[i])
    22.                 dp[j] = dp[j];
    23.             else
    24.                 dp[j] = max(dp[j] , dp[j-w[i]]+c[i]);
    25.         }
    26.         
    27.     cout << dp[v] << endl;
    28.     return 0;
    29. }

    第三个：与第二个一样，中间把状态转移方程合并在了一起；

    1. #include <iostream>
    2. #include <algorithm>
    3.  
    4. using namespace std;
    5.  
    6. const int maxn = 1010;
    7. int dp[maxn];
    8. int w[maxn],c[maxn];
    9.  
    10. int main()
    11. {
    12.     int n,v;
    13.     cin >> n >> v;
    14.     
    15.     for(int i=1;i<=n;++i)
    16.         cin >> w[i] >> c[i];
    17.     
    18.     for(int i=1;i<=n;++i)
    19.         for(int j=v;j>=w[i];--j)
    20.         {
    21.                 dp[j] = max(dp[j] , dp[j-w[i]]+c[i]);
    22.         }
    23.         
    24.     cout << dp[v] << endl;
    25.     return 0;
    26. }

    3. 完全背包问题

    有 N

    种物品和一个容量是 V

    的背包，每种物品都有无限件可用。

    第 i

    种物品的体积是 vi，价值是 wi

    。

    求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
    输出最大价值。

    输入格式

    第一行两个整数，N，V

    ，用空格隔开，分别表示物品种数和背包容积。

    接下来有 N

    行，每行两个整数 vi,wi，用空格隔开，分别表示第 i

    种物品的体积和价值。

    输出格式

    输出一个整数，表示最大价值。

    数据范围

    0


    0

    输入样例

    1. 4 5
    2. 1 2
    3. 2 4
    4. 3 4
    5. 4 5

    输出样例：

    10

     

    /**
     * 完全背包问题，每次考虑第i种物品的时候，能够选择若干件，所以在最开始
     * 求dp[i][j] 的最大值的时候，我们要把选择0，1，……，k件第i种物品的情况
     * 都要进行比较；
     * 这就是最初始的朴素代码：
     * for(int i=1;i<=n;++i)
            for(int j=0;j<=v;++j)
                for(int k=0;k*w[i]<=j;++k)
                    dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i]]+k*c[i]);
        //注意状态转移方程并不是：
        //  dp[i][j] = max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*c[i]);
        //因为 dp[i][j] = max{ dp[i-1][j-k*w[i]] + k*c[i] }(k=0,1,……,k);
        //比较 dp[i][j] 的最大值，那么max 的一个参数肯定是dp[i][j];
        // 但是又得和二重循环的状态转移方程区别开来看；
    */
        
    // 三重循环的朴素方法：

    1. /**
    2.  * 完全背包问题，每次考虑第i种物品的时候，能够选择若干件，所以在最开始
    3.  * 求dp[i][j] 的最大值的时候，我们要把选择0，1，……，k件第i种物品的情况
    4.  * 都要进行比较；
    5.  * 这就是最初始的朴素代码：
    6.  * for(int i=1;i<=n;++i)
    7.         for(int j=0;j<=v;++j)
    8.             for(int k=0;k*w[i]<=j;++k)
    9.                 dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i]]+k*c[i]);
    10.     //注意状态转移方程并不是：
    11.     //  dp[i][j] = max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*c[i]);
    12.     //因为 dp[i][j] = max{ dp[i-1][j-k*w[i]] + k*c[i] }(k=0,1,……,k);
    13.     //比较 dp[i][j] 的最大值，那么max 的一个参数肯定是dp[i][j];
    14.     // 但是又得和二重循环的状态转移方程区别开来看；
    15. */ 
    16.     
    17. // 三重循环的朴素方法：
    18.  
    19. #include <iostream>
    20. #include <algorithm>
    21.  
    22. using namespace std;
    23.  
    24. const int maxn = 1010;
    25. int w[maxn],c[maxn];
    26. int dp[maxn][maxn];
    27.  
    28. int main()
    29. {
    30.     int n,v;
    31.     cin >> n >> v;
    32.     for(int i=1;i<=n;++i)
    33.         cin >> w[i] >> c[i];
    34.     
    35.     for(int i=1;i<=n;++i)
    36.         for(int j=0;j<=v;++j)
    37.         {
    38.             dp[i][j] = dp[i-1][j];  //不选第i种物品
    39.             
    40.             for(int k=1;k*w[i]<=j;++k)  //第i种物品选择若干种
    41.                 dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i]]+k*c[i]);
    42.         }
    43.                 
    44.     cout << dp[n][v] << endl;
    45.     return 0;
    46. }

    // 二重循环的朴素方法：
    /**
     * 因为 dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]]+c[i] ,
     * dp[i-1][j-w[i]*2]]+2*c[i],……,)
     *
     * 又因为 dp[i][j-w[i]]=max(dp[i-1][j-w[i]] , dp[i-1][j-2*w[i]]+c[i]],
     * dp[i-1][j-3*w[i]]+2*c[i], ……,)；
     * 所以 dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]);
    */

    1. // 二重循环的朴素方法：
    2. /**
    3.  * 因为 dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]]+c[i] , 
    4.  * dp[i-1][j-w[i]*2]]+2*c[i],……,)
    5.  * 
    6.  * 又因为 dp[i][j-w[i]]=max(dp[i-1][j-w[i]] , dp[i-1][j-2*w[i]]+c[i]],
    7.  * dp[i-1][j-3*w[i]]+2*c[i], ……,)；
    8.  * 所以 dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]);
    9. */
    10.  
    11. /**
    12. #include <iostream>
    13. #include <algorithm>
    14.  
    15. using namespace std;
    16.  
    17. const int maxn = 2010;
    18. int dp[maxn][maxn];
    19. int w[maxn],c[maxn];
    20.  
    21. int main()
    22. {
    23.     int n,v;
    24.     cin >> n >> v;
    25.     
    26.     for(int i=1;i<=n;++i)
    27.         cin >> w[i] >> c[i];
    28.     
    29.     for(int i=1;i<=n;++i)
    30.         for(int j=0;j<=v;++j)
    31.         {
    32.             if(j<w[i])
    33.                 dp[i][j]=dp[i-1][j];
    34.             else
    35.                 dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);
    36.         }
    37.     
    38.     cout << dp[n][v] << endl;
    39.     return 0;
    40. }
    41. */


    // 滚动数组优化；
    // dp[j] = max(dp[j],dp[j-w[i]]+c[i]);

    1.  
    2. // 滚动数组优化；
    3. // dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
    4.  
    5. #include <iostream>
    6. #include <algorithm>
    7.  
    8. using namespace std;
    9.  
    10. const int maxn = 2010;
    11. int dp[maxn];
    12. int w[maxn],c[maxn];
    13.  
    14. int main()
    15. {
    16.     int n,v;
    17.     cin >> n >> v;
    18.     
    19.     for(int i=1;i<=n;++i)
    20.         cin >> w[i] >> c[i];
    21.     
    22.     for(int i=1;i<=n;++i)
    23.         for(int j=0;j<=v;++j)
    24.         {
    25.             if(j<w[i])
    26.                 dp[j]=dp[j];
    27.             else
    28.                 dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
    29.         }
    30.     
    31.     cout << dp[v] << endl;
    32.     return 0;
    33. }

    4. 多重背包问题 I

    有 N

    种物品和一个容量是 V

    的背包。

    第 i

    种物品最多有 si 件，每件体积是 vi，价值是 wi

    。

    求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
    输出最大价值。

    输入格式

    第一行两个整数，N，V

    ，用空格隔开，分别表示物品种数和背包容积。

    接下来有 N

    行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i

    种物品的体积、价值和数量。

    输出格式

    输出一个整数，表示最大价值。

    数据范围

    0


    0

    输入样例

    1. 4 5
    2. 1 2 3
    3. 2 4 1
    4. 3 4 3
    5. 4 5 2

    输出样例：

    10

     * 由于每种物品有s[i]件可以选择，所以并不能优化成二重循环；
     * 这就和完全背包的三重循环朴素做法是差不多的思想，只是在第三个for循环
     * 那儿判断k是否没有超过s[i]；

    1. /**
    2.  * 由于每种物品有s[i]件可以选择，所以并不能优化成二重循环；
    3.  * 这就和完全背包的三重循环朴素做法是差不多的思想，只是在第三个for循环
    4.  * 那儿判断k是否没有超过s[i]；
    5. */
    6.  
    7. /**
    8. #include <iostream>
    9. #include <algorithm>
    10.  
    11. using namespace std;
    12.  
    13. const int maxn = 110;
    14. int w[maxn],c[maxn],s[maxn];
    15. int dp[maxn][maxn];
    16.  
    17. int main()
    18. {
    19.     int n,v;
    20.     cin >> n >> v;
    21.     
    22.     for(int i=1;i<=n;++i)
    23.         cin >> w[i] >> c[i] >> s[i];
    24.         
    25.     for(int i=1;i<=n;++i)
    26.         for(int j=0;j<=v;++j)
    27.             for(int k=0;k*w[i]<=j && k<=s[i];++k)   
    28.                 dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i]]+k*c[i]);
    29.                 
    30.     cout << dp[n][v] << endl;
    31.     return 0;
    32. }
    33. */

     * 把多重背包切成 0 1 背包问题；
     *
        for(int j=1;j<=s;++j)   
            for(int k=v;k>=w;--k)
                dp[k]=max(dp[k],dp[k-w]+c);
                
        把s件相同的物体看成01背包中s种不同的物体，
        目的就是为了降低空间复杂度，时间复杂度是差不多的；

    1. /**
    2.  * 把多重背包切成 0 1 背包问题；
    3.  * 
    4.     for(int j=1;j<=s;++j)   
    5.         for(int k=v;k>=w;--k)
    6.             dp[k]=max(dp[k],dp[k-w]+c);
    7.             
    8.     把s件相同的物体看成01背包中s种不同的物体，
    9.     目的就是为了降低空间复杂度，时间复杂度是差不多的；
    10. */
    11.  
    12.  
    13. #include <iostream>
    14. #include <algorithm>
    15.  
    16. using namespace std;
    17.  
    18. const int maxn = 110;
    19. int w[maxn],c[maxn],s[maxn];
    20. int dp[maxn];
    21.  
    22. int main()
    23. {
    24.     int n,v;
    25.     cin >> n >> v;
    26.     
    27.     for(int i=1;i<=n;++i)
    28.     {
    29.         int w,c,s;
    30.         cin >> w >> c >> s;
    31.         
    32.         for(int j=1;j<=s;++j)   //把s件相同的物体看成01背包种s种不同的物体，目的就是为了降低空间复杂度，时间复杂度是差不多的
    33.             for(int k=v;k>=w;--k)
    34.                 dp[k]=max(dp[k],dp[k-w]+c);
    35.     }
    36.                 
    37.     cout << dp[v] << endl;
    38.     return 0;
    39. }

    5. 多重背包问题 II

    有 N

    种物品和一个容量是 V

    的背包。

    第 i

    种物品最多有 si 件，每件体积是 vi，价值是 wi

    。

    求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
    输出最大价值。

    输入格式

    第一行两个整数，N，V

    ，用空格隔开，分别表示物品种数和背包容积。

    接下来有 N

    行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i

    种物品的体积、价值和数量。

    输出格式

    输出一个整数，表示最大价值。

    数据范围

    0


    0 0

    提示：

    本题考查多重背包的二进制优化方法。

    输入样例

    1. 4 5
    2. 1 2 3
    3. 2 4 1
    4. 3 4 3
    5. 4 5 2

    输出样例：

    10

     

     * 状态设计：dp[i][j]：从前i种物品中选择不超过容量j的集合中价值最大的
     * 方案；
     * 状态计算：dp[i][j] = { dp[i-1][j-k*w[i]] + k*c[i] };
     *
     * 每种物品有s件，每种物品选择k件，难道k真的需要从 0 枚举到 s 吗？
     * 其实并不需要，我们可以用二进制来优化；
     * 因为32位的二进制位可以表示的数是（0 —— 2^32 -1），那么我们用合适的
     * 二进制组合一定能表示（0——s）的所有数；
     *
     * 假设s用二进制表示的组合是：1，2，4，8，...，2^k，t;(t>=0 && t<2(k+1))
     * （即 s = 1+2+4+8+...+2^k+t )，其中2^k表示的是
     * s用二进制表示的最后一个，也是最大的一个完整的二次方幂；
     * 那么有 2^(k+1)-1 <= s && 2^(k+2)-1 > s 一定成立；
     *
     * 因此可得分解s的过程如下：
     *  int k=1;
        while(k<=s)
        {
            ++idx;
            w[idx] = k*a;
            c[idx] = k*b;
            s-=k;
            k*=2;
        }
        if(s > 0)
        {
            ++idx;
            w[idx] = s*a;
            c[idx] = s*b;
        }
        
        因此分解完所有的物品以后，就可以看作是 01背包来解决；

    1. /**
    2.  * 状态设计：dp[i][j]：从前i种物品中选择不超过容量j的集合中价值最大的
    3.  * 方案；
    4.  * 状态计算：dp[i][j] = { dp[i-1][j-k*w[i]] + k*c[i] };
    5.  * 
    6.  * 每种物品有s件，每种物品选择k件，难道k真的需要从 0 枚举到 s 吗？
    7.  * 其实并不需要，我们可以用二进制来优化；
    8.  * 因为32位的二进制位可以表示的数是（0 —— 2^32 -1），那么我们用合适的
    9.  * 二进制组合一定能表示（0——s）的所有数；
    10.  * 
    11.  * 假设s用二进制表示的组合是：1，2，4，8，...，2^k，t;(t>=0 && t<2(k+1))
    12.  * （即 s = 1+2+4+8+...+2^k+t )，其中2^k表示的是
    13.  * s用二进制表示的最后一个，也是最大的一个完整的二次方幂；
    14.  * 那么有 2^(k+1)-1 <= s && 2^(k+2)-1 > s 一定成立；
    15.  * 
    16.  * 因此可得分解s的过程如下：
    17.  *  int k=1;
    18.     while(k<=s)
    19.     {
    20.         ++idx;
    21.         w[idx] = k*a;
    22.         c[idx] = k*b;
    23.         s-=k;
    24.         k*=2;
    25.     }
    26.     if(s > 0)
    27.     {
    28.         ++idx;
    29.         w[idx] = s*a;
    30.         c[idx] = s*b;
    31.     }
    32.     
    33.     因此分解完所有的物品以后，就可以看作是 01背包来解决；
    34. */
    35.     
    36. #include <iostream>
    37. #include <algorithm>
    38.  
    39. using namespace std;
    40.  
    41. const int N = 25000,M = 2100;
    42. int w[N],c[N];  //N=2000*log(2000) 
    43. int dp[M];
    44.  
    45. int main()
    46. {
    47.     int n,v;
    48.     cin >> n >> v;
    49.     
    50.     int idx=0;
    51.     for(int i=1;i<=n;++i)
    52.     {
    53.         int a,b,s;
    54.         cin >> a >> b >> s;
    55.         
    56.         int k=1;
    57.         while(k<=s)
    58.         {
    59.             ++idx;
    60.             w[idx] = k*a;
    61.             c[idx] = k*b;
    62.             s-=k;
    63.             k*=2;
    64.         }
    65.         if(s > 0)
    66.         {
    67.             ++idx;
    68.             w[idx] = s*a;
    69.             c[idx] = s*b;
    70.         }
    71.     }
    72.     n = idx;
    73.     
    74.     for(int i=1;i<=n;++i)
    75.         for(int j=v;j>=w[i];--j)
    76.             dp[j] = max(dp[j] , dp[j-w[i]]+c[i]);
    77.             
    78.     cout << dp[v] << endl;
    79.     return 0;
    80. }

    9. 分组背包问题

    有 N

    组物品和一个容量是 V

    的背包。

    每组物品有若干个，同一组内的物品最多只能选一个。
    每件物品的体积是 vij

    ，价值是 wij，其中 i 是组号，j

    是组内编号。

    求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

    输出最大价值。

    输入格式

    第一行有两个整数 N，V

    ，用空格隔开，分别表示物品组数和背包容量。

    接下来有 N

    组数据：

    • 每组数据第一行有一个整数 Si

    ，表示第 i

    • 个物品组的物品数量；
    • 每组数据接下来有 Si
    • 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j
      • 个物品的体积和价值；

      输出格式

      输出一个整数，表示最大价值。

      数据范围

      0
      0 0

      输入样例

      1. 3 5
      2. 2
      3. 1 2
      4. 2 4
      5. 1
      6. 3 4
      7. 1
      8. 4 5

      输出样例：

      8

    /**
     * dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i][k]]+c[i][k]);
    */

    // 二维数组进行状态设计

    1. /**
    2.  * dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i][k]]+c[i][k]);
    3. */
    4.  
    5. // 二维数组进行状态设计
    6. #include <iostream>
    7. #include <algorithm>
    8.  
    9. using namespace std;
    10.  
    11. const int maxn = 110;
    12. int s[maxn],w[maxn][maxn],c[maxn][maxn];
    13. int dp[maxn][maxn];
    14.  
    15. int main()
    16. {
    17.     int n,v;
    18.     cin >> n >> v;
    19.     
    20.     for(int i=1;i<=n;++i)
    21.     {
    22.         cin >> s[i];
    23.         for(int j=1;j<=s[i];++j)
    24.             cin >> w[i][j] >> c[i][j];
    25.     }
    26.     
    27.     for(int i=1;i<=n;++i)
    28.         for(int j=0;j<=v;++j)
    29.         {
    30.             dp[i][j] = dp[i-1][j];  //不选第i种
    31.             for(int k=1;k<=s[i];++k)
    32.             {
    33.                 if(j>=w[i][k])  //选择第i种的第k号编号
    34.                     dp[i][j] = max(dp[i][j],dp[i-1][j-w[i][k]]+c[i][k]);
    35.             }
    36.         }
    37.  
    38.     cout << dp[n][v] << endl;
    39.     return 0;
    40. }

     

    /**
     * dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i][k]]+c[i][k]);
    */

    // 一维数组（滚动数组）进行状态设计

    1. /**
    2.  * dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i][k]]+c[i][k]);
    3. */
    4.  
    5. // 一维数组（滚动数组）进行状态设计
    6. #include <iostream>
    7. #include <algorithm>
    8.  
    9. using namespace std;
    10.  
    11. const int maxn = 110;
    12. int s[maxn],w[maxn][maxn],c[maxn][maxn];
    13. int dp[maxn];
    14.  
    15. int main()
    16. {
    17.     int n,v;
    18.     cin >> n >> v;
    19.     
    20.     for(int i=1;i<=n;++i)
    21.     {
    22.         cin >> s[i];
    23.         for(int j=1;j<=s[i];++j)
    24.             cin >> w[i][j] >> c[i][j];
    25.     }
    26.     
    27.     for(int i=1;i<=n;++i)
    28.         for(int j=v;j>=0;--j)
    29.         {
    30.             dp[j] = dp[j];  //不选第i种
    31.             for(int k=1;k<=s[i];++k)
    32.             {
    33.                 if(j>=w[i][k])  //选择第i种的第k号编号
    34.                     dp[j] = max(dp[j],dp[j-w[i][k]]+c[i][k]);
    35.             }
    36.         }
    37.  
    38.     cout << dp[v] << endl;
    39.     return 0;
    40. }

  • 相关阅读:
    使用Spyder进行动态网页爬取：实战指南
    【Java从入门到精通 04】：Java标识符命名及关键字、保留字
    linux 设备树的由来与使用
    进程的控制
    浏览器缓存机制
    2022牛客多校4 K NIO‘s Sword
    设计定时任务实现数据同步的最佳实践
    ESP-RTC方案乐鑫ESP32-S3音视频通信应用，启明云端乐鑫代理商
    Java web入门：在Idea上创建Java web项目
    Scrum敏捷开发方法
  • 原文地址：https://blog.csdn.net/qq_51825761/article/details/126922170