#include<stdio.h> int f[2099][2099]; int w[2099]; int c[2099]; int max(int a,int b) { if(a>b) return a; else return b; } int main() { int T; int i,j; int n,v; scanf("%d",&T); while(T--) { for (i = 0; i < 2099; i++) for (j = 0; j < 2099; j++) f[i][j]=0; scanf("%d%d",&n,&v); for(i=1;i<=n;i++) scanf("%d",&w[i]); for(i=1;i<=n;i++) scanf("%d",&c[i]); for(i=1;i<=n;i++) for(j=0;j<=v;j++) { if(j>=c[i]) f[i][j]=max(f[i-1][j-c[i]]+w[i],f[i-1][j]); else f[i][j]=f[i-1][j];//这点WA了N次 跟QGX大侠搞了无数次终于发现问题 } printf("%d\n",f[n][v]); } return 0; }
二维数组代码可以优化为1维