C++-利用记忆化搜索实现完全背包

Question

对于完全背包问题，有没有基于备忘的非递推解决方案？

Answer 1

理论上来讲,在不考虑栈溢出的情况下, 所有基于递推的动态规划都可以通过记忆化搜索实现的。递推和记忆化搜索只是求解的两种顺序而已.

根据转移方程,设计出一种求解顺序,保证每一个状态在求解时,它所依赖的状态已被求解.这种按照顺序,从已知状态一步步推出未知状态的方法我们可以称为递推.

当我们不设计求解顺序, 而直接从问题出发, 如果当前状态所依赖的状态没有求解, 则先求解所依赖的状态, 直到所有状态已被求解, 这种方法我们称为基于备忘的动态规划, 或者称之为“记忆化搜索”.

对于完全背包问题, 设
- N为物品种数
- M为背包体积
- w[i]为第i件物品的体积
- v[i]为第i件物品的收益
利用动态规划求解, 状态表示为dp[i, j],表示前i种物品在使用了j的体积时能获取的最大权值.易得状态转移方程
dp[i, j] = max{dp[i-1, j-k * w[i]] + k * v[i] | j - k * v[i] >= 0}
则总问题的解为dp[N, V].边界情况很简单, 不再赘述.

如果采用记忆化搜索, 可知每一个状态所依赖的状态. 容易写出如下代码:

int DP(int index, int vol)
{
if (dp[index][vol] != -1) // -1 表示还没求解过
return dp[index][vol];
if (vol == 0 || index == 0)
return 0;
for (int i = 0; i * w[index] <= vol; i++)
dp[index][vol] = max(dp[index][vol],
DP(index-1, vol-i*w[index]) + i*v[index]);
return dp[index][vol];
}

求解时,调用DP(N, V)即可.

第一次发答案，如有不妥，欢迎指教。
吐槽下网站的编辑器是在太渣了。