AcWing 2. 01背包问题(记忆化搜索)
原题链接
简单
作者:
星星.
,
2023-02-13 22:54:05
,
所有人可见
,
阅读 159
01背包问题用记忆化搜索的方式来代替循环写
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int f[N][N];
int v[N],w[N];
//每个物品只有两种选择,拿这个物品或者不拿这个物品
int dp(int i,int j)
{
if(f[i][j]!=-1) return f[i][j];
//因为只能用一次所以如果这个物品已经被用过了,就返回
if(i-1==n) return 0;
//由于物品是从1开始的所以最后一个物品是i-1,判断与n是否相等
//物品搜索到最后一件没了,那就返回0
f[i][j]=dp(i+1,j);
//与循环写法类似,在不算第i个物品时每个物品都是加1然后看下一个
if(v[i]<=j)
//只有当最后一个物品体积还是小于j时,才进行这一步
f[i][j]=max(dp(i+1,j),dp(i+1,j-v[i])+w[i]);
//每一步路都是dp递归着走下一步,每一步路都是走完这一步看下一步
//这里i+1相当于循环里的i++,递归相当于循环,然后函数的初值就是初值
//取每个路线的最大值
return f[i][j];
}
int main()
{
memset(f,-1,sizeof f);
cin>>n>>m;
for(int i=1;i<=n;i++)
//用的i=1,所以下面物品i也是从1开始调用
{
cin>>v[i]>>w[i];
}
cout<<dp(1,m);
//从1开始
//0是物品数,刚开始进去遍历的物品数为0,就是i
//m是总体积,就是j
return 0;
}