Дано: n одинаковых предметов известным образом размещены в m пронумерованных ящиках. Пустых ящиков нет. Нужно достать k таких предметов, причём операция извлечения для разных ящиков имеет разный вес. Есть ли оптимальный алгоритм извлечения предметов, чтобы суммарный вес был минимальным ?

(0) Так извлекай все k предметов из самого дешевого ящика.

(1) а если там нет столько предметов?

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

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

(3)

Ну и в чем проблема? Считаешь себестоимость ящиков, сортируешь в пордке возрастания. И начинаешь обходить. Если количество в ящике больше чем k - пропускаешь(для ускорения можно удалить из списка этот ящик), иначе открываешь ящик и уменьшаешь k на количество из ящика и возвращаешься в начало обхода.

(5) + сортируешь в порядке возрастания себестоимости.

(0) Задача разовая? В смысле надо достать 1 раз k1 предметов и все? Или потом будет k2,k3,k4 и так далее. Стратегии возможно разные.

(5) Проблема в (3): в 1-ом (дешевом) ящике - 1 предмет, во 2-ом (дорогом) - 2. Нужно отобрать 2 предмета.
Если действовать жадным - получим 1 предмет из 1-ого, второй - из 2-ого. В результате может получиться дороже, чем 2 из 2-ого.

(8) Объясняю, что значит слова: "считаешь себестоимость" - делишь цену ящика на количество. Сортируешь поэтому параметру и обходишь список.

(9) Тогда это будет не исходная задача, т.к. выборка 1 ящика из 2-ого будет в 2 раза дешевле.

Там не все так просто,могут быть варианты.
В общем случае,задача решается полным перебором.
например,может быть один дорогой ящик на 5 пиедметов,а два более дещевых на 2 и на 3 дадут тоже количество,но при меньших затратах

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

Похоже на что-то складское: набрать нужное количество из разных ячеек. Озвучьте характерные параметры в реальной ситуации:
- сколько может быть различных ящиков m;
- порядок k;
- насколько сильно могут отличаться "стоимости".
Может быть реально решить полным перебором или эффективно применить схему ветвей и границ.
Навскидку не приходит на ум какая-либо из "классических" переборных задач.

(10) Приведи конретный приме с количеством, ос стоимостями.

(11) > Там не все так просто,могут быть варианты.

Могут. Допустим если осталось подобрать 1шт., а остались ящики в которых по 5-10 штук, а можно некоторым сочетанием подобрать точно к. Но ресурсов потребуется больше.

Но полный перебор ресурсов затребует больше.

(12) Да, это складское. Товар раскидан по стеллажам. Некоторые коробки прямо под носом, а за некоторыми нужно далеко залезть. Но если, например, нужно отгрузить 10 штук, а в близких ("дешёвых") коробках осталось по 1 штуке, что вполне возможно, т.к. они самые ходовые, то проще один раз залезть в полную дальнюю ("дорогую") коробку и достать всё скопом, чем собирать по одной штуке из десяти ближних коробок.

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

Ну и, учитывая специфику, на абсолютную оптимальность здесь можно забить.

(15) Вряд ли овчинка стоит выделки (пытаться найти оптимальное решение).
Складские работники могут исходить из других соображений: например, порядок на складе.
В качестве "прототипа", наверное, вполне подойдет "жадный" из (5).

(4) За наводку спасибо. Как оказалось, простого решения нет. Посмотрю, стоит ли реализовывать "рюкзак". Скорее всего сделаю  сортировку и перебор первых вариантов.

(18) Рюкзак это когда ты из ящика забираешь всё, в твоей задаче ты берешь сколько надо (только платишь за всё). ИМХО это совсем не "рюкзак".

(19) Давайте решим под-задачу:

Есть три ящика,
в одном Р деталей,
в другом О деталей.
в третьем Т деталей


Стоимость  одной детали Х, цена открытия первого ящика Р*X
Стоимость  одной детали У, цена открытия второго ящика О*У
Стоимость  одной детали Я, цена открытия второго ящика Т*Я

Х<У<Я

Понятно, что может быть такое сочетание когда лучше взять не из самого дешевого.

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

(20) Для каждого оптимального значения стоимости будет существовать решение с не более чем одним частичным взятием. При этом могут быть решения с несколькими частичными взятиями для той же суммы.

Видимо, можно предположить, что есть оптимальное решение, в котором частично берется только из ОДНОГО ящика.
Примерно так: пусть есть решение (х1,х2,х3) и х1<Р и х2<О (взяли не полностью).
Тогда решение (Р,х1+х2-Р,х3) имеет не большую стоимость (перекинули часть из 2 в 1).

(21) ПРимер?

(21) Так в каком варианте может быть выгодно взять из двух ящиков частично?

(24) Похоже, что ни в каком.

(25) Значит это возвращается нас к обычному перебору.

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

Отсортировать все ящики по весу (слева дешевые, справа дорогие):

1) набрать товар из самых дешевых ящиков (слева на право)
2) попробовать взять ВЕСЬ ("К") товар из одного ящика (если такое возможно и если ящиков несколько - берем из самого дешевого)

3) уменьшить количество товара "К"  на число товара в самом дешевом ящике (самом левом), пока "К">0 выполнять 1) и 2).

Веса в 1) и 2) запоминать для каждой комбинации. Выбрать минимальный вес из получившегося результата. Ну и проверку на "зацикливание" не забыть)

(0) http://www.mathelp.spb.ru/book1/lprog3.htm

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

(30) ещё раз: равнооптимальные решения существуют. Среди них обязательно есть решение (скорее несколько) с одним частичном ящиком, кроме случая с попаданием в цель без излишка.

Есть ощущение, что мы друг друга не понимаем.

(29) Так сформулируйте задачу ТС как задачу ЛП: у меня не получается.

(31)> авнооптимальные решения существуют.

Ну и кому они нужны?

Ты написал:
> в твоей задаче ты берешь сколько надо (только платишь за всё). ИМХО это совсем не "рюкзак".

Если более оптимальных решений - нет. То все решается простым перебором.

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

Остановился на таком варианте. Сортирую ячейки по возрастанию веса. Потом делаю не более 6! перестановок. Для практической задачи этого д.б. достаточно. Обычно товары лежат в нескольких ячейках, максимум 9.

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

Процедура КнопкаВыполнитьНажатие(Кнопка)
    КолвоСтрок=5;
    
    a=Новый ТаблицаЗначений;
    a.Колонки.Добавить("Буква");
    
    Для й=1 По КолвоСтрок Цикл
        a.Добавить();
        a[й-1].Буква=й;
    КонецЦикла;
    
    generate(a,0,КолвоСтрок);
КонецПроцедуры

Процедура generate(a,t,n)
    if t=n-1 Тогда //Вывод очередной перестановки
        Текст="";
        Для й=1 По n Цикл
            Текст=Текст+a[й-1].Буква;
        КонецЦикла;
        Сообщить(Текст);
    Иначе
        Для j=t По n-1 Цикл //Запускаем процесс обмена
            Если j<>t Тогда
                a.Сдвинуть(a[j],t-j);
                a.Сдвинуть(a[t+1],j-t-1);
            КонецЕсли;
            t=t+1;
            
            generate(a,t,n); //Рекурсивный вызов
            
            t=t-1;
            Если j<>t Тогда
                a.Сдвинуть(a[j],t-j);
                a.Сдвинуть(a[t+1],j-t-1);
            КонецЕсли;
        КонецЦикла;
    КонецЕсли;
КонецПроцедуры

(35) > максимум 9.

512вариантов для полного перебора. С возвратом назад и того меньше.

Перебертся за смешное время. Ладно бы речь шла о 100.

9!=362880

Все равно кладовщик будет пользоваться старым добрым FIFO (или LIFO).