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

请教一道算法题

  •  
  •   lcj2class · 155 天前 · 1156 次点击
    这是一个创建于 155 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Given an array with positive integers and another integer for example {7 2 4} and 9, you are required to generate an equation, by inserting operator add ("+") and minus ("-") among the array. The left side of equation are consist of the array and the right side of equation is the integer. Here the result is 7-2+4=9.

    无意间在 http://www.raychase.net/1285 里看到的,作者没去说这题的思路。除了穷举外,还有什么好方法呢 🤔

    9 回复  |  直到 2019-01-22 17:18:45 +08:00
        1
    geelaw   155 天前 via iPhone
    这个问题(很直白地)是 subset sum,数字都很小的时候用最常见的那个 dynamic programming。此外还可以用 @ChaoXu 之前的研究结果。

    该问题是 NP-hard,所以不要期待一个多项式时间的算法。
        2
    enenaaa   155 天前
    @geelaw 请教下为啥数字大的时候不能用动态规划
        3
    guyeu   155 天前
    emmmm 这个问题比 subset sum 多了个限定条件,感觉用二叉树+剪枝可以试试。
        4
    geelaw   155 天前 via iPhone
    @enenaaa #2 数字大的时候动态规划不如枚举有效率
        6
    qinyusen   155 天前
    @geelaw 额,刚才 at 错人了。。。
        7
    aijam   155 天前
        8
    lcj2class   155 天前
    @geelaw #4 是说数字大的时候会有额外的 overhead,有没有相关文章介绍的呢?
        9
    geelaw   154 天前 via iPhone
    @lcj2class 举个例子,有 n 个数,最大的数大小是 3^n,则 DP 的时间复杂度是 Omega(3^n) 但枚举的时间复杂度是 O(2^n*poly(n))。

    如果你用“刷新式”实现动态规划则另谈。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3806 人在线   最高记录 5043   ·   Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 23ms · UTC 07:45 · PVG 15:45 · LAX 00:45 · JFK 03:45
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1