最低金额，重新审视.(不是最小子数组总和)

Question

给定一个数字 n，一个数组 arr 我想提取最小数量的整数以达到 n，并从 arr 中删除我使用的数字。用一个例子来解释得更好。给定 n = 13 且 arr = [8,0,2,2,3,1,1,1,3,1] 我必须从 arr 中删除总和为 13 的最小整数数。

我的策略是按降序对 arr 进行排序，因此 arr 将是 [8,3,3,2,2,1,1,1,1,0]，然后我开始从第一个数字迭代到最后一个数字，并在我到达 n 时爆发，在本例中为 13。鉴于我们的例子，我将以 8,3,3 结尾，因为我已经在 13 岁了。但问题来了，紧随 3 之后的是 2，如果我选择 2 而不是 3(8 + 3 + 2 = 13(，我将节省更多。我说节省更多，因为这个问题是另一个巨大问题的一部分，为了成功实施它，我需要尽可能少。如果在两个的地方，我说5，我的排序方法就很好了。而且，我想删除我用来获取总和的数字并将它们保存在另一个数组中，称之为 arr1。因此，对于此示例，结果应为 arr = [3,2,1,1,1,0] 且 arr1 = [8,3,2]。谁能帮我？我的 Python 代码看起来像这样(假设列表已经排序(：

n = 13
arr1 = []
arr = [8,3,3,2,2,1,1,1,0]
for i in xrange(len(arr)):
if sum(arr1) < n:
arr1.append(arr[0])
del arr[0]
else:
break
print arr,arr1

这将打印 [2,2,1,1,1,0] [8,3,3]。但我希望它打印 [8,3,2] [3,2,1,1,1]

Answer 1

这应该有效

n = 13
arr1 = []
arr = [8,3,3,2,2,1,1,1,0]
for i in arr:
if sum(arr1)+i <= n:
arr1.append(i)
arr.remove(i)
if sum(arr1) == n:
break
print arr,arr1