Search code examples
pythonalgorithmgrouping

I have problem i cannot solve the python grouping problem


How to write a code in Python language according to the following instructions:

  1. Int values will be received from the user. When the user enters the value 0, the value retrieval process will be finished.
  2. The entered values will be stored in an array.
  3. Groups must have a minimum number of groups, with the sum of the elements of each group being less than 70
  4. Groups will be printed on the screen.

I wrote but it is not working. What is the promblem of the code? Which part of the code should I edit?

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

Inputs:

400
10
700
200
600
490
160
300
200
320

My Outputs:

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

But the output should be:

700
600 100
490 200
400 300
320 200 160

Solution

  • Here's a greedy implementation: https://reintech.io/blog/python-bin-packing-problem-guide.

    • Like you already figured out, you need to sort the list first.
    • Afterwards, you add each number to the first group it fits in, creating new groups when necessary.
    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 is a reference here, that when modified updates the corresponding group in groups
    • sum(group): sum calculates the sum of the numbers in the group
    • for...else: the else block gets executed if the loop completes its iterations without encountering a break statement.
    • print(*group): the * operator unpack the numbers from the group passing the as arguments to the print function

    As @Unmitigated pointed out, it's greedy, so it doesn't work for [3, 3, 2, 2, 2, 2]:

    3 3
    2 2 2
    2
    

    Expected:

    3 2 2
    3 2 2
    

    Non-greedy implementation (using 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]: this puts every number in a separate group.
    • for permutation in permutations(numbers): this iterates over all permutations of numbers.