典型的01背包
DP方程: dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]);
#include<iostream> #include<stdio.h> #include<string.h> #include<string> using namespace std; int T; int N,V; int value[1005]; int volume[1005]; int dp[1005]; int main() { scanf("%d",&T); while(T--) { memset(dp,0,sizeof(dp)); scanf("%d%d",&N,&V); //录入价值 for(int i=1;i<=N;++i) scanf("%d",&value[i]); //录入体积 for(int i=1;i<=N;++i) scanf("%d",&volume[i]); //DP for(int i=1;i<=N;++i) for(int j=V;j>=volume[i];--j) dp[j]=max(dp[j],dp[j-volume[i]]+value[i]); printf("%d/n",dp[V]); } return 0; }
