算法 - python 给定一个正整数a和一个包含任意个正整数的 列表 b，求所有<=a 的加法组合

Question

例如，10,[1,2,3]

输出类似：
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 +2 + 2
3 + 3 + 3 + 2
3 + 2 + 2 + 2 + 1

注意：是小于等于，list 内的正整数有可能并不能正好等于 a.

Answer 1

Kami menulis kod yang lebih pendek melalui itertools.combinations_with_replacement:

def solve2(lst, bound):
    max_length = bound // min(lst)
    for n in range(1, max_length+1):
        for c in itertools.combinations_with_replacement(lst,n):
            if sum(c) <= bound:
                print('+'.join(map(str, c)))
            
solve2([1,2,3], 10)

Answer 2

Anggap bahawa masalah itu memenuhi andaian berikut:

1. Elemen dalam senarai boleh digunakan semula

2. Selagi gabungan kurang daripada atau sama dengan had atas, ia boleh diterima, walaupun jauh kurang daripada had atas atau pun sifar

Berikut ialah undang-undang ganas:

# code for python3

from itertools import combinations

def solve(lst, upperbound):
    candidates = []
    for n in lst:
        for count in range(upperbound//n):
            candidates.append(n)
    allcomb = set()
    for l in range(1, len(candidates)+1):
        for comb in combinations(candidates, l):
            if not comb in allcomb:
                allcomb.add(comb)
                if sum(comb) <= upperbound:
                    print('+'.join([str(n)for n in comb]))
        
solve([1,2,3], 10)

---

Soalan yang saya jawab: Python-QA