01背包暴力dfs与记忆化

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m;//n表示有几个物品，m表示背包能装的空间 

int jz[1010],wz[1010];//jz表示物品的价值，wz表示物品所占的空间 

int fun(int x1,int y1)//x1表示枚举到第几个物品，是边界，y1表示背包还剩下多少空间，用来确定这个能不能装

{

if(x1>n) return 0;

else if(y1<wz[x1]) return fun(x1+1,y1);//超过重量不能装，只能考虑下一个

else if(y1>=wz[x1])

{

return max(fun(x1+1,y1-wz[x1])+jz[x1],fun(x1+1,y1));

} 

} 

int main()

{

cin>>n;

cin>>m; 

for(int k=1;k<=n;k++)

{

cin>>wz[k]>>jz[k];

}

int res=fun(1,m);

cout<<res;

 } 

记忆

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m;//n表示有几个物品，m表示背包能装的空间 

int jz[1010],wz[1010];//jz表示物品的价值，wz表示物品所占的空间 

int f[1010][1010];

int fun(int x1,int y1)//x1表示枚举到第几个物品，是边界，y1表示背包还剩下多少空间，用来确定这个能不能装

{

if(f[x1][y1]) return f[x1][y1];

int sum=0;

if(x1>n) sum=0;

else if(y1<wz[x1]) sum=fun(x1+1,y1);

else if(y1>=wz[x1])

{

sum=max(fun(x1+1,y1-wz[x1])+jz[x1],fun(x1+1,y1));

} 

f[x1][y1]=sum;

return sum;

} 

int main()

{

cin>>m;

cin>>n; 

for(int k=1;k<=n;k++)

{

cin>>wz[k]>>jz[k];

}

int res=fun(1,m);

cout<<res;

 }