zeyexe
V2EX  ›  问与答

请教解题思路请教算法

  •  
  •   zeyexe · Jan 2, 2014 · 4023 views
    This topic created in 4707 days ago, the information mentioned may be changed or developed.
    有一组数,(23, 35.5, 26.5, 100, 76, 236.4, 100, 55.5, 238, 410.5, ... ...) 等等,都是大于0的,怎么选出其中的几个数相加,使和大于某个数(比如说 562),且和与这个数值的差值最小。就是说怎么求 (x+y+z+j+k+ ... +p+q)-562=diff,当x, y, z, j, k, p ,q等为哪些值时,差值diff的值最小。

    求解题思路求算法,本来数学就不好,何况毕业这么多年了...
    6 replies  •  1970-01-01 08:00:00 +08:00
    Ultratude
    Ultratude
    Jan 2, 2014 via iPhone❤️1
    1
    第一感觉用 DP 吧。
    Golevka
    Golevka
    Jan 2, 2014❤️1
    2
    LS+1, 提示: 对于原问题, 不难找到一个与之等价的0-1规划问题.
    wxstorm
    wxstorm
    Jan 2, 2014❤️1
    3
    subset sum问题,应该NPC的。
    你这个感觉更难
    zeyexe
    zeyexe
    OP
    Jan 2, 2014
    4
    @Ultratude
    @Golevka
    @wxstorm

    多谢各位提点,我先去了解一下这些问题和算法。
    marklrh
    marklrh
    Jan 2, 2014❤️1
    5
    想了一会儿,感觉还是要向Dynamic Programming: knapsack problem 的方向去想
    http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
    liuchang0812
    liuchang0812
    Jan 2, 2014❤️1
    6
    首先,你要给出明确的数据范围,其次才能给出算法。
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   2145 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 60ms · UTC 13:58 · PVG 21:58 · LAX 05:58 · JFK 08:58
    ♥ Do have faith in what you're doing.