#include<iostream>#include<cstring>#include<algorithm>using namespace std;int dp[1000][1000];//大數(shù)組聲明為全局變量才不會(huì)報(bào)錯(cuò)int main(){	int T;	cin>>T;	while(T--){		int n,w;		cin>>n>>w;		int value[1000],cost[1000];		memset(dp,0,sizeof(dp));		for(int i=1;i<=n;i++) {cin>>value[i];}		for(int i=1;i<=n;i++) {cin>>cost[i];}		for(int i=1;i<=n;i++){//枚舉物品			for(int j=0;j<=w;j++){if(j>=cost[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost[i]]+value[i]);			    else dp[i][j]=dp[i-1][j];			}		}		cout<<dp[n][w]<<endl;			}	return 0;} dp[i][j]表示把前i件物品中選取若干件物品放入剩余空間為j的背包中所能得到的最大價(jià)值，首先考慮第i件物品放還是不放，如果不放，問(wèn)題變成求解從前i-1件物品中挑選物品放入空間j中獲得的最大值是多少；如果放， 問(wèn)題則變成求出從前i-1件物品中挑選物品放入空間j-cost[i]中獲得的最大值是多少，從而再加上第i件物品的價(jià)值。但是無(wú)論如何，要想求出dp[i]都要先求出dp[i-1],所以主循環(huán)是i遞增到n。因?yàn)楫?dāng)考慮前i件物品時(shí)，背包剩余的體積不是固定的（方法的不同造成的），所以第二層循環(huán)要枚舉背包的體積（從0開(kāi)始）。其實(shí)就相當(dāng)于列了一張n*w+1的表，把每一種情況都算了出來(lái)存到dp數(shù)組里