01背包问题深度理解

问题描述

有n件物品和一个容量为v的背包,求可以得到的最大价值。其中重量是w[i],价值是v[i]。

例  4 5

      1 2

      2 3

      3 4

      2 2

01背包问题的常用的f[v]=max(f[v],f[v-w[i]]+v[i])的解法是由树递归得来的,这里从头推演一遍。

递归求解:

我们可以这样理解,我们从第一个物品开始,每个物品都有两种情况:选或不选,于是就有下图:

01背包问题深度理解

从此我们可以设函数res(int i,int j)(i表示第几个物品,j表示背包剩余容量),不断的判断选还是不选,不断地递归调用,直到i=n+1时,就开始回溯,逐层返回得到的最大价值,最终获得背包能装下的最大价值。

由此我们可以写出递归求解的代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=101;
int w[maxn],v[maxn],n,w1;
int res(int i,int j)
{
    int ans=0;   //保存每一步求得的当前最大价值
    if(i==n+1)
        return ans;   // 当到n+1个物品时就开始回溯
    if(w[i]>j)
        ans=res(i+1,j);  //若当前物品的重量大于背包容量时,就无法放入背包
    else
       ans=max(res(i+1,j),res(i+1,j-w[i])+v[i]);//若能放下,则取放入或不放入两种情况中较大值
    return ans;
}
int main()
{
    scanf("%d%d",&n,&w1);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&w[i],&v[i]);
    cout<<res(0,w1)<<endl;
    return 0;
}

但是,我们可以知道这样求得复杂度O(n)=2^n,此时已经超时了,所以我们需要优化代码。

我们从上图中可以发现,在每一步都有很多重复调用的过程(用红笔画出的格子都是需要重复调用的),所以这样会有很多的重复的计算,我们可以发现出去相同的在每一层最多会有v+1个,因为就只能会有res(i,5)、res(i,4)、res(i,3)、res(i,2)、res(i,1)、res(i,0)这几种情况,所以除去相同的之后的复杂度为n*v,复杂度大大降低。

我们可以通过引入dp数组来保存计算过的结果,然后每次调用时都判断该状态是否已经被计算过了,若计算过了就可以直接返回结果。

此时的代码为:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=101;
const int maxw=10003;
int w[maxn],v[maxn],n,w1,dp[maxn][maxw]; //引入dp数组保存已经计算过的结果
int res(int i,int j)
{    
    //判断这种情况是否被计算过,若被计算过就可以直接返回结果不用进行下面的一系列判断计算
    if(dp[i][j]>0)
       return dp[i][j];
    int ans=0;
    if(i==n)
        return ans;
    if(w[i]>j)
        ans=res(i+1,j);
    else
        ans=max(res(i+1,j),res(i+1,j-w[i])+v[i]);
    dp[i][j]=ans; //保存求出结果
    return ans;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&n,&w1);
    for(int i=0;i<n;i++)
        scanf("%d%d",&w[i],&v[i]);
    cout<<res(0,w1)<<endl;
    return 0;
}

我们由此又可以得出打表的方法即:

    for i = 1.......n

          for j =1....v

                dp[i][j]=max(dp[i-1][ j ] ,dp[ i-1 ][ j-w[ i ] ] + v[ i ]);

再对空间复杂度进行优化可得:

      for i = 1.......n

            for j =v....p[i]

                  dp[ j ]= max( dp[ j ] ,dp[ j-w[ i ] ] + v[ i ]);

因此就得到了我们现在常用的计算01背包的方法。

我们还应该注意初始化的细节问题

 我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。 有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背 包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。 如果是第一种问法,要求恰好装满背包,那么在初始化时除了F[0]为0,其 它F[1..V ]均设为−∞,这样就可以保证最终得到的F[V ]是一种恰好装满背包的 最优解。 如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该 将F[0..V ]全部设为0。

这是为什么呢?可以这样理解:初始化的F数组事实上就是在没有任何物 品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量 为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”,其它容量的 背包均没有合法的解,属于未定义的状态,应该被赋值为-∞了。如果背包并非 必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的 价值为0,所以初始时状态的值也就全部为0了。