#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;
int ans[3][13000];
int main()
{
int n,m,w[3403],d[3403];
while(scanf("%d%d",&n,&m)!=EOF)
{
// printf("%d",sizeof(ans));
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&d[i]);
for(int i=0;i<=m;i++)
{
if(w[1]<=i)ans[1][i]=d[1];
else ans[1][i]=0;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j>=w[i])
ans[2][j]=max(ans[1][j],ans[1][j-w[i]]+d[i]);
else ans[2][j]=ans[1][j];
}
for(int j=0;j<=m;j++)
ans[1][j]=ans[2][j];
}
printf("%d\n",ans[2][m]);
}
return 0;
}
同3356一样，今天的DP简单上路题。
这里有一个地方需要注意一下，就是滚动数组，最开始开的数组是ans[3000][13000]提交得到的是内存超了，后来想到了对滚动数组的应用