如题,比如像一维背包问题,目的是选出价值最大的方案,满足重量不超过背包重量(一个约束条件),那如果是二位背包,满足背包的可承受的重量和体积要求(满足 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
维数的数量和空间是指数关系啊
多维背包这种问题如果用搜索可以试试模拟退火,效果很好 |