【OJ】DP 01背包 记忆化搜索 O(nW)

题目链接：<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;
}