题目链接:<a target=_blank href="http://hzu.acmclub.com/index.php?app=problem_title&id=538&problem_id=6042">点击打开链接</a> /* 01背包 记忆化搜索 O(nW) */ #include<iostream> #include<algorithm> #include<string.h> #define MAX_N 101 #define MAX_W 3001 using namespace std;//最多有3000元,dp[][3001]<-solve(0,3000) int w[101],v[101],n,W,dp[MAX_N][MAX_W]; int solve(int i,int ww){ if(dp[i][ww]>=0)return dp[i][ww];//已有,直接返回 if(i==n) return dp[i][ww]=0; else if(ww<w[i])return dp[i][ww]=solve(i+1,ww); else return dp[i][ww]=max(solve(i+1,ww),solve(i+1,ww-w[i])+v[i]); } int main(){ freopen("DP 01.txt","r",stdin); int num=0,t;cin>>t; while(t--){ num++; memset(dp,-1,sizeof(dp));//memset int只能0和-1,能所有char int ans=0;cin>>W>>n; for(int i=0;i<n;i++)cin>>w[i]; for(int i=0;i<n;i++)cin>>v[i]; ans=solve(0,W); cout<<"Case #"<<num<<": "<<ans<<endl; for(int i=0;i<=n;i++){ for(int j=0;j<=W;j++) printf("%3d",dp[i][j]); putchar('\n'); } } return 0; }