当前位置: 代码迷 >> 综合 >> 关于背包dp的思考
  详细解决方案

关于背包dp的思考

热度:78   发布时间:2024-01-16 23:16:32.0

这篇文章是本人学习背包dp的阶段性总结,涵盖了本人的心路历程和思考:

总结一:枚举的方式及本质。

考虑状压dp。

当n比较小时(n <= 128),忽略是否合法,完全可以用一串二进制数字表示选择方案。

如:

当n = 7时,0001101即可表示选择了第1,3,4件物品(从右开始)。

而由于多数情况下,n > 128,导致使用状压会超过c/c++的最大范围__int128,即不能使用状压。

但这种枚举的思想,却是奠定了记忆化搜索的基础。

总结二:背包dp自记忆化搜索而生。

初学背包dp时,最先接触的一定是最经典的01背包:

  相关解决方案