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,.... фигачим повторно еще и с этими банками.... ошибся, не ту подсунул и получил картину маслом - пикасо... а если красим на заводе бэху мера города (ну такая вот картинка у нас)... во веселуха получится... серо-буро-малиновый попугай....