anvano,

1. Упрощаем условия для наглядности:
- картинок будет 6 (а не 1 000)
- оттенков будет 7 (а не 100)
- для печати картинки используется 2-3 оттенка (а не 30)
- количество заливаемых банок краски 4 (а не 30)
2. Заполняем массив очередной порции картинок (чем больше, тем лучше) для сбора статистики и получаем статистику использования оттенков для печати данного набора картинок (см. пример):
- Оттенок 1 используется 2 раза
- Оттенок 2 используется 4 раза
- Оттенок 3 используется 3 раза
- Оттенок 4 используется 4 раза
- Оттенок 5 используется 1 раз
- Оттенок 6 используется 1 раз
- Оттенок 7 используется 0 раз
3. Заполняем 4 банки оттенками используемые по статистике набора максимально:
Это банки с оттенками 1, 2, 3, 4 ПРИЧЕМ ! приблизительно (согласно коеффициентам) банку с оттенком 1 заполняем примерно наполовину, банку с оттенком 2 заполняем полностью, банку с оттенком 3 заполняем примерно на две трети… (можно пристреляться, поточнее зная расход на картинку оттенка)
3. Печатаем:
Соответственно будут распечатаны картинки: 1, 2, 3, 5, 6
4. Печатаем остаток – картинку 4:
- очищаем пустую банку с оттенком 1 (мы ее целиком и не заправляли и у нее минимальный коэффициент) и заливаем в нее четверть (согласно коэффициенту) оттенок 5
- очищаем почти пустую банку с оттенком 3 (мы ее заправляли на две трети и снова минимальный коэффициент) и заливаем четверть (согласно коэффициенту) оттенок 6.
Печатаем…
5. Моем почти все пустые банки для перехода на новую порцию картинок.
Примечание:
Не утверждаю, что это оптимально (первое что пришло в голову), но уверен, что от этого можно оттолкнуться… может кто-то предложит и получше...

anvano,

Второй способ - итерационный / интерактивный: Позволяет печатать в реальном времени картинки, с учетом поступления во время печати новых картинок.

1. Вычисляем набор оттенков из максимального количества банок в 30 штук, которые позволяют распечатать
максимальное количество картинок из текущего набора картинок.
2. Заполняем банки и печатаем...
3. Добавляем новые картинки.
4. Выполняем пункт 1, но уже очищаем не используемые банки и заливаем в них новые оттенки и опять печатаем...
Итак пункты 3 и 4 в цикле...

anvanovmag,

Спасибо, я думал о распределении по встречаемости.
Но тут смущает вероятность наткнуться на распределение, при котором загрузив 4 наиболее часто встречающихся цвета мы не сможем вообще ни одной картинки напечатать.

Хотя при увеличении количества картинок такая вероятность стремится к нулю

Неудачный ваш пример (на счет ни одной картинки).... у вас 30 банок на 15 оттенков за картинку (в 2 раза больше перекрытие), по этому в примере вашем неудачном на каждую картинку (пропорционально) должно быть не 4 банки а минимум 6 - 8 и тогда опять все напечатается за один заход... по этому первый вариант можно отмести только после виртуального прогона на реальных данных... так любую идею можно зарубить на корню....

аптимизаторэлементарщина

да наверное не совсем так...

В конце получится 50 картинок, которые никуда... и придется чтоб распечатать каждую перед каждой картинкой пере заправлять все банки... вот тут то краске и пипец... очень наглядно в этом смысле решение транспортной задачи, в которой если идти таким способом получается самый не оптимальный результат, а оптимал как раз заключается в том, что нужно выбирать не всегда самые весомые узлы дабы общий вес узлов был максимален... например можно выбрать узлы с максимума по убыванию 5, 5, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1 (последние как раз и есть сами по себе) и удельный вес узлов будет 28, а можно выбрать узлы 4, 4, 4, 3, 5, 4, 4, 3, 2, 3, 4, 4 и удельный вес узлов будет 44 что гораздо больше.... так и с краской будет - первые десять картинок распечатали с одним набором банок, а оставшиеся 50 картинок будем печатать с заменой всех банок перед каждой картинкой... вот это оптимизация будет...

anvano,

В общем случае это больше комбинаторика, по этому вот это:

anvanoЛадно завтра учебник по теорверу с полки достану

Скорее всего ни к чему...

Задача схожа с задачей выиграть в спортлото типа 5 из 36, только выигрышная комбинация не одна,
а несколько и они все известны (это наборы оттенков, описывающие картинки)...
Ну и сама задача состоит в том, что нужно так зачеркнуть карточки с 30 вариантами ответов (максимальное количество используемых банок) из возможных 100 вариантов оттенков, чтобы количество этих карточек было минимально (то есть минимальное количество заправок) для покрытия всех выигрышных комбинаций (печати всех картинок)

Alibek B.А растеризация делается? Или в палитре оттенков чистые цвета?

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

оптемезаторих можно печатать в 2 прохода (возможно, и больше)

Да выход... но это дополнительный учет: какую картинку в какие проходы посылать дополнительно и сколько раз... типа банки поменяли, значит напечатанные картинки 5, 7, 15,.... фигачим повторно еще и с этими банками.... ошибся, не ту подсунул и получил картину маслом - пикасо... а если красим на заводе бэху мера города (ну такая вот картинка у нас)... во веселуха получится... серо-буро-малиновый попугай....

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


miksoftглавное, чтобы время вычислений было меньше времени на "лишние" смены красок, а то не окупится :)

Попробуй крутиться только в наборе картинок, иначе действительно компа и мощей не хватит....
1. Разложить палитру каждой картинки и N картинок и получить массив вариантов банок:
картинка1 : Банки - 1, 5, 7, 8, 33, 45, 48, 56, 60
картинка2 : Банки - 3, 4, 6, 7, 21, 34, 35, 39, 44, 49, 56, 77, 88, 99
.............................................................................................
картинка2 : Банки - 5, 6, 9, 10, 22, 35, 36, 40, 48, 50, 57, 79, 98, 99, 100
2. Ну а потом группировать только этот конечный набор картинок в максимальные количества банок 30 шт., дабы минимальным количеством вариантов по 30 банок покрыть все наборы картинок...

softwarermiksoftИ, судя по входным данным и моим ощущениям, этих ошметков вполне может быть достаточно много - единицы, а иногда и десятки процентов от всего набора. А если так, то они могут дать значительно число перезаправок, т.е. сильно влиять на итоговый результат.
Могут. Тем не менее, общая идея имхо остаётся той же - нужно найти минимальное число "кластеров", в которые улягутся все картинки. В частности, те картинки А и Б, которые Вы рассматриваете, таки имеют пересечения по цветам с какими-то другими картинками, то есть условно близки какому-то из кластеров.


Вода в ступе... обо всем этом говорилось в первом десятке реплик... и от того, что теперь об этом говорить другими словами (кластерами - шмастерами) - ничего не изменится.... нужно просто действительно дождаться реального примера от ТС а не тупо тролить типа кто заумнее....

anvanoНу это я такую постановку задачи выбрал просто :) надо же было кейс придумать.

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


anvanoДа, всё-таки поступило уточнение, нельзя картинку повторно пропечатать на другом наборе красок.
Так что считаем, что это скорее ткацкий станок с нитями и каждое изделие должно быть целиком соткано на заправленном наборе нитей

Это мля скорее всего новый вид ПРО с разными ракетами, ясен пень - все самолеты и ракеты нужно сбивать с первого раза....

anvanoВот пример реальных тестовых данных.
Первая строка - номера красок (их тут 70 разных)
Первый столбец - названия картинок
единицы - краска используется в картинке
нули - не используется

кому нужны данные в виде бд для удобства то качайте mdb в формате Акцесс 2000...
- таблица Лист1 собственно данные из экселя, просто добавил счетчик в начало и поле выбора в конец...
- запрос (Использование банок в картинках) покажет сколько раз банка используется при печати 25 картинок...

- Пример скорее всего не совсем реальный (банки представлены по убыванию рейтинга использования и нет ни одной банки, которая не используется вообще)....
- но есть вышеупомянутые хвосты (банки с 46 по 70 используются всего один раз) см. запрос