最简单的就是利用搜索,把每一种情况都考虑。
//深度搜索。复杂度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));
i......
阅读全文