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])的解法是由树递归得来的,这里从头推演一遍。
递归求解:
我们可以这样理解,我们从第一个物品开始,每个物品都有两种情况:选或不选,于是就有下图:
从此我们可以设函数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了。