V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
chunrong918
V2EX  ›  程序员

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

  •  
  •   chunrong918 · 2017-10-07 10:50:58 +08:00 · 4786 次点击
    这是一个创建于 2604 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

    谢谢!

    4 条回复    2017-10-07 11:20:52 +08:00
    ayyll
        1
    ayyll  
       2017-10-07 11:08:09 +08:00
    DP 本身就是空间换时间吧。。既想省时间又想省空间,试试深搜+剪枝?
    20015jjw
        2
    20015jjw  
       2017-10-07 11:17:19 +08:00 via Android
    我觉得 lz 这是题没刷够想太多
    vegito2002
        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 都可以做, 但是不保证时间。 当然如果要自己实现, 可以加上剪枝, 尤其是可以维护一个全局最大值, 来剪掉无法改变当前最大值的分枝。
    lksltjw
        4
    lksltjw  
       2017-10-07 11:20:52 +08:00   ❤️ 1
    维数的数量和空间是指数关系啊

    多维背包这种问题如果用搜索可以试试模拟退火,效果很好
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1078 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 19:06 · PVG 03:06 · LAX 11:06 · JFK 14:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.