这是一个创建于 4003 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一组数，(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 条回复 • 1970-01-01 08:00:00 +08:00
 |
1
Ultratude 2014-01-02 13:26:27 +08:00 via iPhone  1
第一感觉用 DP 吧。
|
 |
2
Golevka 2014-01-02 13:32:02 +08:00 1
LS+1, 提示: 对于原问题, 不难找到一个与之等价的0-1规划问题.
|
 |
3
wxstorm 2014-01-02 13:38:19 +08:00 1
subset sum问题，应该NPC的。
你这个感觉更难 |
 |
5
marklrh 2014-01-02 14:25:02 +08:00 1
想了一会儿，感觉还是要向Dynamic Programming: knapsack problem 的方向去想
http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/ |
 |
6
liuchang0812 2014-01-02 21:48:41 +08:00 1
首先，你要给出明确的数据范围，其次才能给出算法。
|
Select Language