01背包问题,从暴力到最优解
首先就是递归暴力写法,DFS,对于一个物品有取或不取两种选择,会有2的n次方个分支。
很简单的DFS写法,也过不了,因为时间复杂度太大。
可以练习一下DFS。
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
const int N = 1001;
// w是weight,v是value
int w[N],v[N];
// 第一个参数是拿到第几个物品,第二个是背包剩余重量
// 递归结束条件 i== n,下标上说,说最后一个物品的下一个
int rec(int i,int j){
if(i == n) return 0;
int result = 0;
if(w[i] <= j){
// 可取
// 注意后面的rec有加v[i]
result = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
}else{
//不可取
result = rec(i+1,j);
}
// 返回结果
return result;
}
int main(){
cin >> n >> m;
for(int i = 0;i<n;i++) cin >> w[i] >> v[i];
cout << rec(0,m) <<endl;
}
现在开始,我们的第一次优化(参考白皮书)。
如果你把上面那个递归的树画出来的话,你会发现,假如n很大,会有很多分支重复进行
了递归,我们要优化的就是,如果这个参数已经验证过结果,就直接访问结果。而不是再进行
递归再次求解。也就是递归剪枝。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1001;
// 二维记忆化数组,[i][j]对应上文的循环中的rec(i,j)
int dp[N][N];
int w[N],v[N];
int n,m;
int rec(int i ,int j){
// 计算过,值就不是-1,直接返回
if(dp[i][j] != -1){
return dp[i][j];
}
int result = 0;
if(i== n) return 0;
if(w[i] <=j){
result = max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
}else{
result = rec(i+1,j);
}
dp[i][j] = result;
return result;
}
int main(){
cin >> n >> m;
//初始化dp数组
// 这里选择-1和memset有关系,建议看一下memset的定义
memset(dp,-1,sizeof(dp));
for(int i = 0;i<n;i++) cin >> w[i] >> v[i];
cout << rec(0,m) <<endl;
}
上述程序,已经可以过了。时间复杂度为o(nW)。记忆化搜索。
但对于递归问题,我们要思考能不能把递归简化为非递归问题。
如果我们仔细想一想上述递归过程,对dp数组进行分析。
我们可以得到一个关于dp数组的递推式:
//结合rec进行思考
dp[n][j] = 0 ; //末端为0
dp[i][j] = {
if(w[i] < j) {
dp[i][j] = dp[i+1][j] ;//拿不了,下一个
}else{
// 可以拿
dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]); //拿或者不拿的最大值
}
}
这里我们注意到一个问题,想要知道dp[i][j]的值,就要知道dp[i+1][j]的,但dp[i+1][j]又是由
dp[i][j]推出的,这样似乎得不出我们想要的答案。
我们从i=n从后向前推理,也就是说,让rec倒着来,反递归,从枝节的末端,一级一级的把答案传回起点。
我们把上述逻辑写为代码如下:
#include <iostream>
using namespace std;
const int N = 1001;
int w[N],v[N];
int dp[N][N];
int main(){
int n,m;
cin >> n >>m ;
for(int i = 0;i<n;i++) cin >> w[i] >> v[i];
for(int i = n-1;i>=0;i--){
for(int j = 0;j<=m;j++){
if(w[i] <= j){
//可以取
// 当i == n-1,i+1取到的都是0,也即是rec(n+1,j)的结束标志
dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
}else{
dp[i][j] = dp[i+1][j];
}
}
}
// 最后的结果就是我们的rec(0,m)了
cout << dp[0][m] <<endl;
}
这一步,就是我们把rec的递归过程理解后,从递归的末端反着推出rec(0,m);
时间复杂度和上面一个相同,但由于不是递归,速度和空间都有一点小提升。
既然可以反着推,总感觉不太好理解,可以不可以正着推呢?
这也是y总的写法。
答案是可以的,只不过递推式要变为
dp[0][j] = 0; //起点
dp[i+1][j] = {
if(可以拿){
dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]+v[i]); //也就是局部最优解向前推
}else{
//不可以拿
dp[i+1][j] = dp[i][j];
}
}
dp[n][m]; //结果
代码如下:
#include <iostream>
using namespace std;
const int N = 1001;
int w[N],v[N];
int dp[N][N];
int main(){
int n,m;
cin >> n >>m ;
for(int i = 1;i<=n;i++) cin >> w[i] >> v[i];
for(int i = 1;i<=n;i++ ){
for(int j = 0;j<=m;j++){
if(w[i] <=j){
// 可以拿
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[n][m] <<endl;
}
1维哥们也不会哈哈哈。
学不动了。
说实话哥们自己都没理解。你要看懂了,也挺神奇的只能说。
只是提供一个思考的新方式。
白皮书是什么啊
挑战程序设计1
哦哦