尋找離開最小剩餘部分的最大號碼

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