如果有多个约束条件，动态规划怎么做

[chunrong918]

如题，比如像一维背包问题，目的是选出价值最大的方案，满足重量不超过背包重量（一个约束条件），那如果是二位背包，满足背包的可承受的重量和体积要求（满足 2 个约束条件），怎么做？

那如果要求多个约束约束呢？

如果是多个约束条件，可以用分支界定法来解决，但是用 DP 在时间和空间上会有比较大的优化。

请问大家，DP 如何处理多个约束条件的情况?

有比较好的对应的参考资料吗？

谢谢！

[ayyll]

DP 本身就是空间换时间吧。。既想省时间又想省空间，试试深搜+剪枝？

[20015jjw]

我觉得 lz 这是题没刷够想太多

[vegito2002]

DP 的优越性本来就是在 subproblem 之间的 overlapping 比较多的时候才更容易提升。 如果 constraint 过多， 那么对于 subproblem 的定义相应的也就会越来越细化， 发生 overlapping 的可能性也就格外小， 这时候 DP 就未必有那么大的优越性了。 通用型的 constraint-based 语言类似 prolog， 最后实际上的做法就是 backtrack 来做， 多少 constraint 都可以做， 但是不保证时间。 当然如果要自己实现， 可以加上剪枝， 尤其是可以维护一个全局最大值， 来剪掉无法改变当前最大值的分枝。

[lksltjw]

维数的数量和空间是指数关系啊

多维背包这种问题如果用搜索可以试试模拟退火，效果很好