学步园

最简单的就是利用搜索，把每一种情况都考虑。

//深度搜索。复杂度O(2^n) 
int dfs(int i,int j)
{
	int res;//剩余的空间量。 
	if(i==n)res=0;//如果i==n则剩余空间量为0。 
	else if(j<w[i]) res=dfs(i+1,j);//如果物品太大，不装进去。 
	else  res=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i]);//装和不装的情况都尝试下。 
	return res;
} 

因为在搜索算法中，重复计算的情况较多，我们可以利用数组，把计算结果记录下来，这样就避免了重复计算。

//记忆化搜索。复杂度O(nw). 
int dp[n+1][w+1];
memset(dp,-1,sizeof(dp)); 
int dfs(int i,int j)
{
	if(dp[i][j]>=0)return dp[i][j];//如果已经算过这个值，直接返回。 
	int res;
	if(i==n)res=0;
	else if(j<w[i])res=dfs(i+1,j);
	else res=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i]);
	return d[i][j]=res;//将结果记录在数组中。 
 } 

根据记忆化搜索的算法我们可以得到递推公式：

dp[n][j]=0;

dp[i][j]=dp[i+1][j]  (j<w[i])

dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])   (其他情况)

//动态规划。复杂度O(nw)
int dp[n+1][w+1];
void solve()
{
for(int i=n-1;i>=0;i--)
 for(int j=0;j<=w;j++){
  if(j<w[i])dp[i][j]=dp[i+1][j];
  else dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
 }
printf("%d\n",dp[0][w]);
}