动态规划解0-1背包问题

淩亂°似流年 2022-05-10 08:58 131阅读 0赞

之前有写贪心法求解0-1背包问题，贪心法思路比较直接，而动态规划则没有那么容易理解。

两种算法思想策略对比

贪心法：

每一步都取局部最优解

动态规划：

不确定当前所放入背包的物品是否会成为最优解成分之一？

当 j < w\[i\] 时（当前容重小于物品重量的）， m(i, j) = m(i-1, j)；

当 j >= w\[i\] 时（当前容重大于物品重量的）, m(i, j) =  max（m\[i-1\]\[j\],m\[i-1\]\[j-w\[i\]+v\[i\]）；

将局部最优解先保留下来，每一步的最优解都会参考上一步的最优解。

为了方便理解，举一个例子：

n=5,W=10

v\[5\]=\{2,2,6,5,4\}

w\[5\]=\{6,3,5,4,6\}

制作表格

行数i代表了第i个背包，列数j代表了在当前所能容纳的最大容量j下，单元格的内容表示背包局部最优价值多少

将每一步的背包价值用w\[i\]\[j\]存储下来。

我们需要一层循环来控制是否将物品放入背包，还需要一层循环来控制背包的容量。只有逐渐扩大背包的容量，逐步增加可放入背包的物品，如此分步，才能得到局部的最优解并将这个解保存下来，并为下一步的最优解提供比较信息。

怎么分析这个表，因为w\[i\]\[j\]的得到要依赖w\[i-1\]\[j\],故要竖着分析。

![70][]

11是怎么来的？我们来分析一下：

第三行较第四行，可选择的放入背包的物品多了重量为5，价值为6的物品。

第二行9代表的是选择了前两个物品，也就是选择了重量分别为2,2，价值为6,3的物品。

显然在纳量为8的情况下，重量2、6，价值为6、5的物品提供的总价值大于重量分别为2,2，价值分别为6,3的物品提供的价值，即将重量为2，价值为3的物品取出，放入重量为6,价值为5的物品，因此得到了11这个局部最优解。

很巧妙的算法思想，让我们来看看它的时间复杂度：O（M\*N）

如果使用DFS思想求解，时间复杂度为O(2^N）

代码如下：

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    class goods
    {
    public:
        int w;//重量
        int v;//价值
        int flag=0;//是否被放入背包的标志
    
        goods(int w1=0,int v1=0)
        {
            w=w1;
            v=v1;
        }
    };
    
    class question
    {
    private:
        int W;
        int n;
        goods *g;
    public:
        question(int w=0,int num=0,goods *b=NULL)
        {
            W=w;
            n=num;
            g=b;
        }
        void KnapSack()//动态规划求解背包问题
        {
            int p[n+1][W+1];//代表背包当前价值
            memset(p,0,sizeof(p));
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=W; j++)//对物品循环
                {
                    if(j>=g[i].w)
                        p[i][j]=max(p[i-1][j],p[i-1][j-g[i].w]+g[i].v);
                    else
                        p[i][j]=p[i-1][j];
                }
            }
             for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=W; j++)//代表对物品循环
                {
                    cout<<p[i][j]<<"  ";
                }
                cout<<endl;
            }
        }
    };
    
    int main()
    {
        goods s[6];
        s[0]=goods(0,0);
        s[1]=goods(2,6);
        s[2]=goods(2,3);
        s[3]=goods(6,5);
        s[4]=goods(5,4);
        s[5]=goods(4,6);
    
        int n=5;
        int W=10;
        question Q=question(W,n,s);
        Q.KnapSack();
    
        return 0;
    }

[70]: /images/20220510/a673aebeac59446097da90f9dbb6dcd5.png