Минимальная перестановка коробок для размещения новой коробки в картонных коробках

Есть n cartons. В каждой коробке может быть несколько коробок. Каждая коробка занимает какое-то место.

Нам дается свободное место, оставшееся в каждой коробке, и список размеров коробок в каждой коробке. Нет ограничений по количеству / размеру коробок в каждой коробке.

Теперь у нас есть новая коробка с size x, которую нужно разместить в любой из коробок. Разрешается перестановка любого количества коробок из коробки в любую другую при условии, что в новой коробке остается место для размещения переставленной коробки.

Мне нужно найти перестановку, которая может быть получена при минимальном движении коробки и может вместить новую коробку.

Меня больше интересует случай, когда новую коробку нельзя разместить ни в одном свободном пространстве любой коробки, и необходима некоторая перестановка, чтобы освободить место для новой коробки.

Input format
x : size of new box
n : no of cartons
    box_no_1 :: free_space, no_of_boxes, box1_size, box2_size, ...
    box_no_2 :: free_space, no_of_boxes, box1_size, box2_size, ...

example:
x : 60
n : 3
    1 :: 10 , 3, 10 , 10 , 30
    2 :: 20 , 2, 20 , 10
    3 :: 50, 3, 10, 30, 20

Answer:: box with size 10 in carton 3 can be moved to carton 1. 
Then new box can be kept in box 3.

Может кто подскажет, как решить эту проблему?

Что ты пробовал? Вы знаете о проблеме с упаковкой в ​​контейнеры? Похоже, что с этим легко справиться с помощью целочисленного программирования с использованием классической формулировки, включающей цель, которая описывает сумму неподвижных ящиков (максимизация).

sascha 11.04.2018 12:09

@sascha Моя проблема немного отличается от проблемы с упаковкой мусора. Предположим, что нигде нет свободного места для размещения нового ящика. Единственный вариант - сделать некоторые перестановки текущих ящиков, чтобы освободить место. Возможно, я неправильно понял ваше предложение. Не могли бы вы привести пример использования бункерной упаковки во входных данных.

Harsh Agarwal 11.04.2018 13:02

Попытайтесь понять формулировку целочисленного программирования, чтобы изменить ее в соответствии с вашими потребностями (это приведет к проблеме осуществимости без цели). Затем добавьте цель, равную сохранению старых позиций. Представление такой задачи обычно включает в себя собственные попытки и идеи, а также то, что пошло не так. Вы должны что-то попробовать.

sascha 11.04.2018 13:07
0
3
91
0

Другие вопросы по теме