请教解题思路请教算法 - V2EX

Home Sign Up Sign In

This topic created in 4540 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

1

Ultratude

Jan 2, 2014 via iPhone

1

第一感觉用 DP 吧。

2

Golevka

Jan 2, 2014

1

LS+1, 提示: 对于原问题, 不难找到一个与之等价的0-1规划问题.

3

wxstorm

Jan 2, 2014

1

subset sum问题，应该NPC的。
你这个感觉更难

4

zeyexe

OP

Jan 2, 2014

@Ultratude
@Golevka
@wxstorm

多谢各位提点，我先去了解一下这些问题和算法。

5

marklrh

Jan 2, 2014

1

想了一会儿，感觉还是要向Dynamic Programming: knapsack problem 的方向去想
http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

6

liuchang0812

Jan 2, 2014

1

首先，你要给出明确的数据范围，其次才能给出算法。

About · Help · Advertise · Blog · API · FAQ · Solana · 5450 Online Highest 6679 ·

Select Language

创意工作者们的社区

World is powered by solitude

VERSION: 3.9.8.5 · 37ms · UTC 07:08 · PVG 15:08 · LAX 00:08 · JFK 03:08
♥ Do have faith in what you're doing.