这是一个创建于 2604 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题，比如像一维背包问题，目的是选出价值最大的方案，满足重量不超过背包重量（一个约束条件），那如果是二位背包，满足背包的可承受的重量和体积要求（满足 2 个约束条件），怎么做？
那如果要求多个约束约束呢？
如果是多个约束条件，可以用分支界定法来解决，但是用 DP 在时间和空间上会有比较大的优化。
请问大家，DP 如何处理多个约束条件的情况?
有比较好的对应的参考资料吗？
谢谢！
 |
1
ayyll 2017-10-07 11:08:09 +08:00
DP 本身就是空间换时间吧。。既想省时间又想省空间，试试深搜+剪枝？
|
 |
2
20015jjw 2017-10-07 11:17:19 +08:00 via Android
我觉得 lz 这是题没刷够想太多
|
 |
3
vegito2002 2017-10-07 11:18:23 +08:00 via iPad  2
DP 的优越性本来就是在 subproblem 之间的 overlapping 比较多的时候才更容易提升。 如果 constraint 过多， 那么对于 subproblem 的定义相应的也就会越来越细化， 发生 overlapping 的可能性也就格外小， 这时候 DP 就未必有那么大的优越性了。 通用型的 constraint-based 语言类似 prolog， 最后实际上的做法就是 backtrack 来做， 多少 constraint 都可以做， 但是不保证时间。 当然如果要自己实现， 可以加上剪枝， 尤其是可以维护一个全局最大值， 来剪掉无法改变当前最大值的分枝。
|
 |
4
lksltjw 2017-10-07 11:20:52 +08:00 1
维数的数量和空间是指数关系啊
多维背包这种问题如果用搜索可以试试模拟退火，效果很好 |
Select Language