Python itertools составляют комбинации с суммой

Question

Заказчиком является компания, которая производит разные куски (разных размеров) деревянного пола. У них есть проблема, что, когда кто-то покупает XXm² в деревянном полу, они должны упаковать его части

Коробка может обрабатывать максимальную сумму 220см. Куски начинаются с 30 см и увеличиваются на 5 см до полного куска 220 см.

Чего я пытаюсь достичь? Лучшее сочетание разных кусочков и размеров в коробке, чтобы у дна была хотя бы большая фигура, иначе коробка может «затормозить». Это потому, что коробка должна иметь сильное дно, чтобы обрабатывать другие части выше.

Да, сказал это. Перейдем к коду!

Клиент вводит кусочки, что-то вроде этого:

[220, 170, 150, 145, 130, 125, 125, 115, 110, 110, 105, 95, 95, 90,
 90, 90, 75, 70, 70, 60, 60, 50, 50, 50, 50, 50, 50, 40]

И один из лучших выходов будет:

['220', '170,50', '150,70', '145,75', '130,90',
 '125,95', '125,95', '115,105', '110,110', '90,90,40',
 '70,50,50,50', '60,60,50,50',]

Я пытаюсь использовать itertools:

from itertools import combinations
for i in range(1, 5): # Maximum 4 pieces
    for comb in combinations(customer_input, i):
        if sum(comb) <= 220 and sum(comb) >= 195:
            print(comb)

Первые отпечатки:

(220,)
(170, 50)
(170, 50)
(170, 50)
(170, 50)
(170, 50)
(170, 50)

Похоже, что он идет правильно, но выводит комбинацию (170, 50) более одного раза. Я думаю, что один подход состоит в том, чтобы перестать пытаться создавать новые комбинации после того, как часть была использована.

Как мне этого добиться?

Answer 1

Это способ сделать то, что я думаю, вы пытаетесь:

from collections import Counter

# Generate all combinations up to n elements without repetitions
# with sum up to max_sum
def combs(p, n, max_sum):
    p = sorted(p, reverse=True)
    return _combs_rec(p, n, max_sum, 0, [], 0)

def _combs_rec(p, n, max_sum, idx, current, current_sum):
    if len(current) > 0:
        yield current_sum, tuple(current)
    prev = None
    if n > 0:
        for i in range(idx, len(p)):
            if p[i] != prev and  current_sum + p[i] <= max_sum:
                current.append(p[i])
                yield from _combs_rec(p, n - 1, max_sum, i + 1, current, current_sum + p[i])
                current.pop()
            prev = p[i]

# Input data
pieces = [220, 170, 150, 145, 130, 125, 125, 115, 110, 110, 105, 95, 95, 90,
          90, 90, 75, 70, 70, 60, 60, 50, 50, 50, 50, 50, 50, 40]
max_group = 4
max_sum = 220

# Get maximum combinations
c = Counter(pieces)
while sum(c.values()) > 0:
    next_sum, next_comb = max(combs(c.elements(), max_group, max_sum))
    c.subtract(next_comb)
    print(f'{next_comb} Sum: {next_sum}')

Вывод:

(220,) Sum: 220
(170, 50) Sum: 220
(150, 70) Sum: 220
(145, 75) Sum: 220
(130, 90) Sum: 220
(125, 95) Sum: 220
(125, 95) Sum: 220
(115, 105) Sum: 220
(110, 110) Sum: 220
(90, 90, 40) Sum: 220
(70, 50, 50, 50) Sum: 220
(60, 60, 50, 50) Sum: 220

Обратите внимание, что это не обязательно дает оптимальное решение.Несмотря на то, что каждая итерация выполняет поиск наилучшей комбинации методом «грубой силы», она все еще остается жадным алгоритмом.Ничто не гарантирует, что выбор лучшей комбинации каждый раз позволит вам получить набор комбинаций с наименьшей общей слабиной.Для этого вам придется искать в глобальном пространстве разделов множества частей.

Answer 2

Это не кодовый ответ, а идея расширить свой кругозор.

К этой проблеме можно обратиться как к проблеме оптимизации, известной как Проблема ранца .

Одним из подходов к решению Knapsack может быть использование динамического программирования (на странице википедии, на которую я ссылаюсь, есть раздел об этом). Есть также много обучающих программ о том, как программировать что-то подобное. Например, вот учебник freecodecamp для динамического решения проблемы рюкзака; это НЕ в Python, но важная часть состоит в том, чтобы понять, как решить проблему такого рода.

Я надеюсь, что это приведет вас в правильном направлении для оптимального решения кода.

Answer 3

Использование set - простое решение, позволяющее избежать дублирования:

customer_input = [220, 170, 150, 145, 130, 125, 125, 115, 110, 110, 105, 95, 95, 90,
 90, 90, 75, 70, 70, 60, 60, 50, 50, 50, 50, 50, 50, 40]

from itertools import combinations
combs = set()
for i in range(1, 5): # Maximum 4 pieces
    for comb in combinations(customer_input, i):
        if sum(comb) <= 220 and sum(comb) >= 195 and comb not in combs:
            print(comb)
            combs.add(comb)

# part of output:
# (220,)
# (170, 50)
# (170, 40)
# (150, 70)
# (150, 60)
# (150, 50)
# (145, 75)