AcWing 2. 01背包问题
原题链接
简单
作者:
PeanoX
,
2024-03-31 09:08:12
,
所有人可见
,
阅读 9
算法1
(带备忘递归)
C++ 代码
# include <cstdio>
# include <iostream>
using namespace std;
const int N=1005;
int n,a[N][2],v,b[N][N];//备忘录b[N][N]//
int max(int a,int b)//比较大小//
{
return a>=b?a:b;
}
int weight(int n,int c)
{
int ans=0,s1=0,s2=0;
if(n<0) return 0;
if(c<0) return -100000;
if(b[n][c]!=0)
return b[n][c];
s1=weight(n-1,c);
s2=weight(n-1,c-a[n-1][0]);
b[n][c]=max(s1,s2+a[n-1][1]);//写入备忘录//
return b[n][c];
}
int main()
{
int i,ans=0;
scanf("%d %d",&n,&v);
for(i=0;i<n;i++)
scanf("%d %d",&a[i][0],&a[i][1]);
ans=weight(n,v);
printf("%d",ans);
return 0;
}//第一次写题解,qwq//