记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int mem[N][N];
int dfs(int x,int prv)
{
int res=0;
if(mem[x][prv]) return mem[x][prv];
if(x>n) return 0;
else if(prv<v[x]) res= dfs(x+1,prv);
//每种物品都有无限件可用,如果该物品被装的话可以从x装
else if(prv>=v[x]) res= max(dfs(x+1,prv),dfs(x,prv-v[x])+w[x]);
mem[x][prv]=res;
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
printf("%d",dfs(1,m));
return 0;
}
从下往上推
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
for(int i=n;i>=1;i--)
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) f[i][j]=f[i+1][j];
else f[i][j]=max(f[i+1][j],f[i][j-v[i]]+w[i]);
}
}
printf("%d",f[1][m]);
return 0;
}
从上往下
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
}
printf("%d",f[n][m]);
return 0;
}
内存优化
完全背包可以多次使用,所以可以优化到一维正序枚举
01背包只能拿一次,不能正序枚举,会破坏规则
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d",f[m]);
return 0;
}