我遇到了无法解决的Python分组问题

Question

如何根据以下说明用Python语言编写代码：

1. 用户将输入整数值。当用户输入0时，输入值的过程将结束。
2. 输入的值将存储在一个数组中。
3. 每组的元素总和必须少于70，并且组的数量要达到最小要求。
4. 这些组将被打印在屏幕上。

我写的代码不工作。代码的问题出在哪里？我应该修改代码的哪一部分？

aray = []
while True:
    a = int(input("Sayı gir:"))
    if a != 0:
        aray.append(a)
    else:
        break


x = 700

aray.sort(reverse=True)
aray2 = aray.copy()
array =[]

target = 700
groups = []
currentGroup = []
currentSum = 0

for number in fonk(x,aray,aray2):
    if currentSum + number <= target:
        currentGroup.append(number)
        currentSum += number
    else:
        groups.append(currentGroup)
        currentGroup = [number]
        currentSum = number

groups.append(currentGroup)

for group in groups:
    print("Group:")
    for num in group:
        print(num, end=" ")
    print()
    
def fonk(x,arr, aray2):
    count = 1
    min = 710
    for in1 in range(len(arr)):
        i = arr[in1]
        flag = False
        jj = 0
        for minfind in aray2:
            if minfind < min:
                min = minfind
        for j in aray2:
            if x >= j:
                flag = True
                jj = j
                aray2.remove(jj)
                break
        if not flag:
            continue
        if x >= jj:
            x -= jj
            array.append(jj)
            if x==0 or x<= min:
                x=700
                count+=1
            continue
        else: 
            x = 700
            count +=1
    
    return array

输入：

400
10
700
200
600
490
160
300
200
320

我的输出：

Group:
700
Group:
600
Group:
490 200
Group:
400 300
Group:
320 200 160
Group:
100

但输出应该是：

700
600 100
490 200
400 300
320 200 160

Answer 1

这里有一个贪心算法的实现：https://reintech.io/blog/python-bin-packing-problem-guide.

• 就像你已经发现的，首先需要对列表进行排序。
• 然后，你把每个数字放到第一个合适的组里，如果没有合适的组，就新建一个组。

from __future__ import annotations

MAX_SUM = 7

numbers: list[int] = []
while True:
    number = int(input("Number:"))
    if not number:
        break

    numbers.append(number)

numbers.sort(reverse=True)
groups: list[list[int]] = []
for number in numbers:
    for group in groups:
        if sum(group) + number <= MAX_SUM:
            group.append(number)
            break
    else:
        groups.append([number])

for group in groups:
    print(*group)

• for group in groups：这里的group是一个引用，当你修改它时，会更新groups中对应的组。
• sum(group)：sum用来计算group中数字的总和。
• for...else：如果循环完成所有迭代而没有遇到break语句，else块就会被执行。
• print(*group)：*运算符会把group中的数字拆开，作为参数传给print函数。

正如@Unmitigated指出的，这个方法是贪心的，所以它对[3, 3, 2, 2, 2, 2]不适用：

3 3
2 2 2
2

期望的结果：

3 2 2
3 2 2

非贪心算法的实现（使用itertools）：

from __future__ import annotations

from itertools import permutations

MAX_SUM = 7

numbers: list[int] = []
while True:
    number = int(input("Number:"))
    if not number:
        break

    numbers.append(number)

numbers.sort(reverse=True)
groups = [[number] for number in numbers]
for permutation in permutations(numbers):
    candidate: list[list[int]] = []
    for number in permutation:
        for group in candidate:
            if sum(group) + number <= MAX_SUM:
                group.append(number)
                break
        else:
            candidate.append([number])
            if len(candidate) >= len(groups):
                break

    if len(groups) > len(candidate):
        groups = candidate

for group in groups:
    print(*group)

• [[number] for number in numbers]：这会把每个数字放到一个单独的组里。
• for permutation in permutations(numbers)：这会遍历numbers的所有排列组合。