Как сообразить алгоритм оптимизации?

В общем суть такая-есть к примеру корзины под фрукты, корзины представлены в таком виде:
М/К-мест в корзине, К/К -количество корзин.
	М/К | К/К
	---------
	20  |   3
	18  |   1
	16  |   2
	14  |   6
	12  |   9
	10  |   2
	8   |  10
	6   |   2
	4   |   3

В одной корзине могут быть только яблоки или только груши, короч ток определенные фрукты. К примеру в одной из корзин на 20 фруктов лежат яблоки 18 штук, во второй груши-20 штук, в третьей 5 персиков. У нас есть еще шесть яблок и 1 груша, их нужно положить в корзины, но они не поместятся в корзины, в которых сейчас лежат яблоки с грушами, нужно переложить фрукты так, чтобы в каждой из корзин лежали только одного вида фрукты. Не могу сообразить алгоритм. В маленьких корзинках тоже есть фрукты, нужно все учитывать
  • Вопрос задан
  • 463 просмотра
Решения вопроса 1
aRegius
@aRegius
Python Enthusiast
Сергей, смотри, может подойдет такой вариант (я опишу общий принцип, реализация кода, ессно, на тебе):

1. Сортируешь фрукты по их количеству, от большего к меньшему (например, 30 яблок, 25 груш, 20 апельсинов, 15 мандаринов, 10 слив, 5 бананов).

2. Заполняешь корзины сверху - вниз (от больших объемов к меньшим). Заполняешь максимально полно - всю корзину, остаток оставляешь пока в стороне, не используешь.

Например:
шаг 1: 30 яблок и 3 корзины по 20... Заполняем 1 корзину полностью, остаток 10 яблок сохраняем на потом, сейчас не используем.
шаг 2: 25 груш и 2 корзины по 20... Заполняем 1 корзину полностью, остаток 5 груш сохраняем на потом, сейчас не используем.
шаг 3: 20 апельсинов и 1 корзина по 20... Заполняем 1 корзину полностью, остатка нет.
шаг 4: 15 мандаринов и 1 корзина по 18... ПРОПУСКАЕМ, ищем вариант заполнения ПОЛНОЙ корзины...
шаг 5: 15 мандаринов и 2 корзинs по 16.. ПРОПУСКАЕМ, ищем вариант заполнения ПОЛНОЙ корзины...
шаг 6: 15 мандаринов и 6 корзин по 14... Заполняем 1 корзину полностью, остаток 1 мандарин сохраняем на потом, сейчас не используем.

и т.д. .........

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

Прогон сверху вниз нужен для того, чтобы рационально использовать корзины - ведь, если есть 1 яблоко, и 2 корзины (20 и 4 мест соответственно), логично положить его в корзину на 4 места.

Как-то так. Я, конечно, не специалист в нативных алгоритмах, возможно есть какой-то "интерполяционный метод кажущейся дисперсии" для решения подобных задач - тут я пас :). Чем смог...
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@sitev_ru
sitev.ru - мой блог ...
Попробуй перебором...
Ответ написан
Добавь ещё один столбик "свободно мест" когда что-то кладёшь, берёшь - его пересчитываешь.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы