大于一个数的唯一和

Question

大于一个数的唯一和

3

我正在尝试编写一段代码，它将获取一个介于1和10之间的数字列表，并找出总和大于或等于10的数字，然后从列表中删除这些数字。这里的关键是：首先需要检查列表中是否有任何10，以及是否有总和为10的任意两个数字，然后是任意三个数字，以此类推直到五个数字。此外，被加起来的数字越低，就越好。因此，在对夫妻进行求和时，需要尽可能少地摆脱数字。到目前为止，我已经成功实现了夫妻之和的计算。

n = input("How many numbers in the list? \n")
throw = []
for i in range(int(n)):
    throw.append(random.randint(1, 10))
throw.sort()
increments = 0
print(throw)
increments += throw.count(10)
throw = list(filter(lambda i: i != 10, throw))

high = len(throw)-1
low = 0
acceptable_couples = []
get_rid = []
while low < high:
    sums = throw[high] + throw[low]
    if sums >= 10:
        increments += 1
        get_rid.append(throw[high])
        get_rid.append(throw[low])
        acceptable_couples.append((throw[high], throw[low]))
        high -= 1
        low += 1
    else:
        low += 1
for i in get_rid:
    throw.remove(i)

我也做了三个一组，想用同样的方法来处理四个和五个：

 while len(throw) >= 3:
    z = 0
    x = list(itertools.combinations(throw, 3))
    for couple in x:
        if sum(couple) >= 10:
            z += 1
            i = list(couple)
            increments += 1
            for j in couple:
                throw.remove(j)
            break
        else:
            continue
    if z == 0:
        break

我希望找到一个更简单的方法来完成这个操作。虽然这个方法是可行的，但对于大量数字而言，它似乎会进行很多无用的计算。有什么想法吗？

- Simons93

我不确定我真正理解这个问题。你有原始提示吗？在我看来，如果列表中所有元素的总和> = 10，则应删除所有元素。不是吗？ - Josh Bothun

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bruno Vermeulen · Answer 1

不确定我是否正确理解了你的问题。我的理解是，你有一组介于1和10之间的数字，并且你需要找到这个集合中加起来大于或等于10的最长子集，然后从原始集合中删除这些数字，直到你不能再找到任何包含两个以上数字的集合。

如果这是正确的解释，那么以下方法应该有效：

import random

n = int(input("How many numbers in the list? \n"))
throw = [random.randint(1, 10) for _ in range(n)]
print(throw)

throw.sort()
list_of_solved_sets = []
sets_found = True

while sets_found:
    _sum = 0
    solved_set = []
    solved_indexes = []
    for index, element in enumerate(throw):
        _sum += element
        solved_set.append(element)
        solved_indexes.append(index)
        if _sum >= 10:
            break

    if len(solved_set) <= 1:
        sets_found = False

    else:
        list_of_solved_sets.append(solved_set)

        for index in reversed(solved_indexes):
            del throw[index]

print('List of solved sets:')
for i, solved_set in enumerate(list_of_solved_sets):
    print(f'   {i+1}: {solved_set}')

注意需要按相反的顺序从列表throw中删除索引！

- Bruno Vermeulen · Answer 2

在这种情况下，也许这将是一个解决方案。伪代码如下：

读取数字列表并从高到低排序
从列表中删除所有数字10，并将其作为解决方案添加
循环直至列表为空
取出列表中最大的数字（由于列表已排序，所以第一个数字是最大的），并将其从列表中移除
检查是否通过添加最小数字可以获得大于或等于10的总和，如果不能，则继续使用更大的数字直到完成循环。如果找到解决方案，则跳出循环，将其添加到解决方案中并从列表中删除解决方案的元素。
如果解决了问题，则跳出循环，并使用列表中的下一个最大数字重复外部while循环。如果未解决问题，则将下一个最大数字添加到总和中，并将其从列表中删除，并再次运行for循环以查找添加较小数字的解决方案

代码

import random

n = int(input("How many numbers in the list? \n"))
throw = [random.randint(1, 6) for _ in range(n)]
print(throw)

throw.sort(reverse=True)
print(throw)

list_of_solved_sets = []

# remove all numbers 10 from the list and add a solution
while throw and throw[0] == 10:
    list_of_solved_sets.append([throw[0]])
    del throw[0]

while throw:

    # take the largest number in the set (which is the first number 
    # as list is sorted) and remove it from the list
    solved_set = [throw[0]]
    _sum = throw[0]
    del throw[0]

    while throw:
        solved = False

        # Check if by adding the smallest number we can get
        # a sum greater or equal to 10 if not go to a bigger number
        # until we complete the loop. Break loop if a solution is found, add
        # to solutions and remove element from the list that solved it
        for j in range(len(throw) - 1, -1, -1):
            if _sum + throw[j] >= 10:
                solved_set.append(throw[j])
                del throw[j]

                list_of_solved_sets.append(solved_set)

                solved = True
                break

        # if solved break and repeat the outer while loop with next biggest number
        # in the list. If not solved then add the next biggest number to the sum and      
        # check if we can find a solution adding smaller numbers running the for 
        #loop again
        if solved:
            break

        else:
            _sum += throw[0]
            solved_set.append(throw[0])
            del throw[0]

print('List of solved sets:')
for i, solved_set in enumerate(list_of_solved_sets):
    print(f'   {i+1}: {solved_set}')

结果示例：

How many numbers in the list?
10
[3, 2, 5, 1, 6, 3, 4, 3, 2, 1]
[6, 5, 4, 3, 3, 3, 2, 2, 1, 1]
List of solved sets:
   1: [6, 4]
   2: [5, 3, 2]
   3: [3, 3, 2, 1, 1]