寻找离开最小剩余部分的最大号码

Question

我希望能够找到进入目标的最小号码。

例如：

target = 100 
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137] 

from itertools import combinations 

def subsets_with_sum(lst, target, with_replacement=False): 

    x = 0 if with_replacement else 1 
    def _a(idx, l, r, t): 
     if t == sum(l): r.append(l) 
     elif t < sum(l): return 
     for u in range(idx, len(lst)): 
      _a(u + x, l + [lst[u]], r, t) 
     return r 
    return _a(0, [], [], target) 

如果我要输入：

subsets_with_sum(vals, 270, False) 

入壳，我将输出：

[[57, 99, 114]] 

然而，如果我输入：

subsets_with_sum(vals, 239, False) 

入壳，我将输出：

[] 

相反，我想输出进入目标人数最多： [137, 101]留下剩余1

有没有办法做到这个？

Answer 1

是的，有一种方法。

取而代之的是线条的：

 if t == sum(l): r.append(l) 
     elif t < sum(l): return 

你想保存最好的结果，类似如下：

better = lambda x, y: x if sum (x) > sum (y) else y 

def subsets_with_sum(lst, target, with_replacement=False): 

    x = 0 if with_replacement else 1 
    def _a(idx, l, r, t): 
     if t >= sum(l): 
      r = better (r, l) 
      for u in range(idx, len(lst)): 
       r = better (r, _a(u + x, l + [lst[u]], r, t)) 
     return r 
    return _a(0, [], [], target) 

---

也就是说，如果该值是小的整数，你的问题（有或没有替代）是knapsack problem的情况，并且使用动态编程有一个渐近更快的解决方案（请参阅链接）。

Answer 2

一种方法是让求和可能的（使用递归）的所有可能的组合，然后找到的总和，这是最接近目标

target = 239 
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137] 

# recursive function to get all possible summations 
# return a dict whose keys are the summation values 
# and values are list of elements that makes up that summation 
def get_all_poss_sums(l): 
    if len(l) == 0: 
     return {0: []} 
    else: 
     i = l.pop() 
     temp_sums = get_all_poss_sums(l) 
     sums = {} 
     for s in temp_sums: 
      sums[s] = temp_sums[s] 
      sums[s + i] = temp_sums[s] + [i] 
     return sums 

# get all possible summation 
all_poss_sums = get_all_poss_sums(vals) 

# find the summation closest to target 
for s in sorted(all_poss_sums.keys(), reverse=True): 
    if s <= target: 
     print all_poss_sums[s] #outputs [101, 137] 
     break