<p>给定一组整数(正的或负的),我怎样才能找到这些数的和到给定值的序列?在</p>
<p>示例:给定一个数字列表<code>[4,-16, 9, 33]</code>,我需要求和<code>17</code>。我可以选择序列<code>[4, 4, 9]</code>(数字可以重用)或<code>[-16, 33]</code>。我想找到一种有效的方法来缩短序列的长度。在</p>
<p>它类似于<code>Subset Sum Problem</code>(<a href="http://en.wikipedia.org/wiki/Subset_sum" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Subset_sum</a>),但在我的例子中,数字可以重用。在</p>
<p>它也有点像分区问题(<a href="https://stackoverflow.com/questions/8330371/find-all-possible-subsets-that-sum-up-to-a-given-number">Find all possible subsets that sum up to a given number</a>),但在我的例子中有负值。在</p>
<p>我当前的贪心算法如下。在每个循环中,我将尝试找到一个使当前和与目标和之间的差最小化的数字。在</p>
<pre><code>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.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(next_int)
print(chain)
</code></pre>