DjangoBB LoFi version

Полная версия: Задача об упаковке в контейнеры

Начало » Центр помощи » Задача об упаковке в контейнеры

SoftwerEnginer

Июнь 10, 2019 15:12:26

Доброго времени суток!

Нужна Ваша помощь в решении задачи об упаковке коробок в контейнеры.

Все на что меня хватило это написать небольшой код создающий список коробок:

from operator import itemgetter

n1 = 16
x1 = 1640
y1 = 800
z1 = 1640
m1 = 694
q1 = 6

n2 = 18
x2 = 1850
y2 = 1110
z2 = 1850
m2 = 822
q2 = 10

n3 = 25
x3 = 2550
y3 = 1610
z3 = 2550
m3 = 1500
q3 = 3

n4 = 20
x4 = 2050
y4 = 1210
z4 = 2050
m4 = 896
q4 = 4

n5 = 22
x5 = 2250
y5 = 1310
z5 = 2250
m5 = 952
q5 = 8

n6 = 0
x6 = 0
y6 = 0
z6 = 0
m6 = 0
q6 = 0

n7 = 0
x7 = 0
y7 = 0
z7 = 0
m7 = 0
q7 = 0

# n* - Номер коробки
# x* - Длина коробки
# y* - Ширина коробки
# z* - Высота коробки
# m* - Масса коробки
# q* - Количество коробок данного типа

boxes = [
    (n1, x1, y1, z1, m1, q1),
    (n2, x2, y2, z2, m2, q2),
    (n3, x3, y3, z3, m3, q3),
    (n4, x4, y4, z4, m4, q4),
    (n5, x5, y5, z5, m5, q5),
    (n6, x6, y6, z6, m6, q6),
    (n7, x7, y7, z7, m7, q7),
]

X = 13600
Y = 2400
Z = 3000
M = 20000
Q = 1

# X - Дина контейнера
# Y - Ширина контейнера
# Z - Высота контейнера
# M - Максимальная загрузка по массе
# Q - Количество контейнеров

container = (X, Y, Z, M, Q)

# Код который сортирует список

boxes = sorted(boxes,key=itemgetter(0))

# Код который умножает 

for row in boxes:

    if row[1] !=0:

# Код который умножает строку на количество коробок

        row = row * row[5]

# Код который выстраивает строки в один столбик

        def split(arr, size):
            arrs = []
            while len(arr) > size:
                pice = arr[:size]
                arrs.append(pice)
                arr = arr[size:]
            arrs.append(arr)
            return arrs

        boxes2 = (split(row, 6))

        #print(barabans2)

        for i in boxes2:
            print(i)

В идеале нужно чтобы коробки сортировались методом перебора (bruteforce) с учетом ограничений по геометрическим параметрам и максимально допустимой массе (коробки класть друг на друга нельзя).

Или хотя бы реализовать в Python такой алгоритм (коробки класть друг на друга нельзя):
1) Создать контейнер
2) Поместить коробку
3) Повторять 2 шаг до тех пор пока не превысит лимит по массе или габаритам контейнера
4) Повторить начиная с 1 шага

+ Надо вывести в Print получившееся количество контейнеров, и количество и номера помещенных в контейнер коробок.

Или Вы можете предложить свое решение.

За ранее благодарен!

JOHN_16

Июнь 10, 2019 17:34:52

Это классический задача про рюкзак. Данная конкретная вариация уже стала классикой. Готовых решений наверняка можно найти с десяточек. Надо только поискать

SoftwerEnginer

Июнь 18, 2019 10:47:42

JOHN_16
Это классический задача про рюкзак. Данная конкретная вариация уже стала классикой. Готовых решений наверняка можно найти с десяточек. Надо только поискать

Я нашел похожее решение, но мне нужно добавить дополнительные параметры в виде высоты, ширины, длинны и массы для предметов и ограничений по высоте, ширине, длине и массе для “рюкзака” + при заполнении первого “рюкзака” нужно создать новый и продолжить заполнять его и.т.д., я без понятия как это можно сделать. Если кто знает объясните пожалуйста.

 #!/usr/bin/env python3
"""0-1 knapsack problem: O(n W) in time, space algorithm"""
from collections import namedtuple
from functools import lru_cache
Item = namedtuple('Item', 'value weight')
items = Item(4, 5), Item(3, 4), Item(3, 2), Item(2, 1)
capacity = 6  # max weight we can put into the knapsack
@lru_cache(maxsize=None)  # cache all calls
def best_value(nitems, weight_limit):
    if nitems == 0:  # no items
        return 0  # zero value
    elif items[nitems - 1].weight > weight_limit:
        # new item is heavier than the current weight limit
        return best_value(nitems - 1, weight_limit)  # don't include new item
    else:
        return max(  # max of with and without the new item
            best_value(nitems - 1, weight_limit),  # without
            best_value(nitems - 1, weight_limit - items[nitems - 1].weight)
            + items[nitems - 1].value)  # with the new item
result = []
weight_limit = capacity
for i in reversed(range(len(items))):
    if best_value(i + 1, weight_limit) > best_value(i, weight_limit):
        # better with the i-th item
        result.append(items[i])  # include it in the result
        weight_limit -= items[i].weight
print(result)
print(best_value.cache_info())