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

Question

[Сергей]

В общем суть такая-есть к примеру корзины под фрукты, корзины представлены в таком виде:

М/К-мест в корзине, К/К -количество корзин.
	М/К | К/К
	---------
	20  |   3
	18  |   1
	16  |   2
	14  |   6
	12  |   9
	10  |   2
	8   |  10
	6   |   2
	4   |   3

В одной корзине могут быть только яблоки или только груши, короч ток определенные фрукты. К примеру в одной из корзин на 20 фруктов лежат яблоки 18 штук, во второй груши-20 штук, в третьей 5 персиков. У нас есть еще шесть яблок и 1 груша, их нужно положить в корзины, но они не поместятся в корзины, в которых сейчас лежат яблоки с грушами, нужно переложить фрукты так, чтобы в каждой из корзин лежали только одного вида фрукты. Не могу сообразить алгоритм. В маленьких корзинках тоже есть фрукты, нужно все учитывать

Comments

[aRegius]

Сергей, а чуть больше информации? У вас 38 корзин всего... Они все заполнены? Все разными фруктами? Под завязку? 6 оставшихся яблок почему нельзя в другую свободную корзину положить? Сколько видов фруктов всего?.... Очень много вопросов...

[Сергей]

aRegius: 6 видов фруктов, перемещать можно хоть как, главное чтобы фрукты не перемешивались в одной корзине), корзин с яблоками может быть к примеру штуки 4, основная задача-чтобы фрукты в одной корзине были одинаковыми). Камеры заполнены где-как, может быть и пустая, может быть на половину полная, может быть полная%)

Answer 1

[aRegius]

Сергей, смотри, может подойдет такой вариант (я опишу общий принцип, реализация кода, ессно, на тебе):

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 места.

Как-то так. Я, конечно, не специалист в нативных алгоритмах, возможно есть какой-то "интерполяционный метод кажущейся дисперсии" для решения подобных задач - тут я пас :). Чем смог...

Comments

[Сергей]

Я примерно так и думал, если честно), уже 2 человека мне такое решение подсказывают), подождем, мож еще поинтереснее что будет), спасибо)

[aRegius]

Т.е., нас уже четверо... Прекрасно!

[Сергей]

aRegius: да норм все ;)

Answer 2

[sitev_ru]

Попробуй перебором...

Comments

[Сергей]

Есть норм решение 100%, перебор-крайность)

[sitev_ru]

Может подойдёт "Транспортная задача" ?

Answer 3

[Оптимус Пьян]

Добавь ещё один столбик "свободно мест" когда что-то кладёшь, берёшь - его пересчитываешь.