学步园

二维。

46ms .4936kb

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;


int T, M, N, V, i, j, dp[1100][1100], value[1100], volume[1100];

void print( )
{
int i, j;
for ( i = 0; i <= N; i++)  {
for ( j = 0; j <= V; j++) 
                printf("%d ",dp[i][j]);
             puts("");
        }
}

int main( )
{
    scanf("%d",&T);
while (T--)
    {
        scanf("%d%d",&N,&V);
        memset(dp, 0, sizeof(dp));
for (i = 1; i <= N; i++)
            scanf("%d",&value[i]);
for (i = 1; i <= N; i++)
            scanf("%d",&volume[i]);
for (i = 1; i <= N; i++)
for (j = 0; j <= V; j++)
if (j >= volume[i])
                dp[i][j] = max (dp[i - 1][j],  dp[i -1][j-volume[i]] + value[i]);
else
                    dp[i][j] = dp[i - 1][j];
//print( );
//puts("*************************\n");
        printf("%d\n",dp[N][V]);
    }
return 0;
}