给定一组整数(正数或负数),如何找到一个数字序列,使其总和为给定值?
例如:给定一个数字列表
这类似于
这也有点像 Partition problem(Find all possible subsets that sum up to a given number),但在我的情况下有负值。
我的当前贪心算法如下。 在每个循环中,我将尝试找到一个数字,使当前总和与目标总和之间的差最小化。
例如:给定一个数字列表
[4,-16, 9, 33]
,我需要总和为 17
。 我可以选择序列 [4, 4, 9]
(数字可以重复使用)或 [-16, 33]
。我正在尝试找到一种有效的方法来减少序列的长度。这类似于
Subset Sum Problem
(http://en.wikipedia.org/wiki/Subset_sum),但在我的情况下,数字可以重复使用。这也有点像 Partition problem(Find all possible subsets that sum up to a given number),但在我的情况下有负值。
我的当前贪心算法如下。 在每个循环中,我将尝试找到一个数字,使当前总和与目标总和之间的差最小化。
integers = [-2298478782, 1527301251, 4, 4078748803, 3388759435,
1583071281, 2214591602, 1528349827, -12, 59460983,
-939524100, -1, 2315255807]
target_sum = 1997393191
difference = target_sum
chain = list()
while difference != 0:
min_abs_difference = abs(difference)
next_int = 0
found = False
for i in integers:
new_abs_diff = abs(i+difference)
if new_abs_diff < min_abs_difference:
found = True
next_int = i
min_abs_difference = new_abs_diff
if not found:
print(difference)
print(chain)
print("Cannot find an integer that makes difference smaller")
break
difference += next_int
chain.append(next_int)
print(chain)