Задача о минимальной стоимости закупки на С/С++

[smishel]

Дано:

Имеется 10 поставщиков и 10 товаров. Каждый поставщик поставляет все товары, но у каждого поставщика разные цены на товары.

Найти: 2 или 3 поставщика (или в общем виде 2<N<10) у которых суммарная закупка этих 10 товаров (по 1 шт.) будет иметь минимальную стоимость.

[Abstraction]

О, интересно. Как понимаю, речь идёт о том, что нужно выбрать не более N прейскурантов из M так, чтобы сумма закупки K позиций была минимальна?
Простейший вариант - полный перебор по всем сочетаниям из M по N. Время (при M>>N) - O(K*M^(N+1)). При M=K=10 это, впрочем, достаточно мало, чтобы не искать лучшего алгоритма.
Дальше мысли вслух.
Можно ли в среднем случае отсечь значимую часть вариантов? Для каждого товара у нас есть упорядоченный список продавцов с ценами. Это позволяет быстро (за O(K*M)) узнать оценку снизу для цены покупки при выкидывании произвольного набора торговцев. Если эта оценка превышает уже найденный вариант - все варианты, выкидывающие этот набор, можно не рассматривать.
Другое направление. Пусть у нас есть множество всех сочетаний из M по N. Возможность перейти от одного сочетания к другому заменой одного столбца создаёт на этом множестве граф переходов. Пусть S - оптимальное решение, а P - "пессимальное" решение, такое, что S достижимо из него переходами, уменьшающими стоимость. Такие переходы выделяют в графе направленный подграф, число вершин в котором, вообще говоря, меньше общего числа вершин графа. К сожалению, не очевидно, каким образом быстро найти P.

[smishel]

Оценка перебора привела к следующим параметрам:

Нужно отобрать, к примеру 3 из 10 поставщиков.

Число вариантов= 120

И посчитать все варианты сумм 10 позиций из 30 вариантов (3 строки по 10 вариантов) = 30 045 015

Итого: 30 045 015 * 120 = 3 605 401 800 вариантов перебора.

Меня это число слегка пугает. А вас?

[Mad_Cat]

Оценка перебора привела к следующим параметрам:

господи(
2 массива 10 на 10
и 2 на 10
считаем в первом суммы по строкам и складываем во второй в 1 строку номер во вторую сумму
сортируем второй массив по возрастанию по второй строке
забираем 2 первых или 3 или сколько там нужно первых столбца(номер и сумму соответственно)
откуда тут

3 605 401 800 вариантов перебора.

[Abstraction]

И посчитать все варианты сумм 10 позиций из 30 вариантов (3 строки по 10 вариантов) = 30 045 015

Как? У нас есть (уже выбранные) 3 торговца. Для каждого товара, находим минимум из 3 величин и прибавляем к сумме. Всё, за ~100 инструкций получили сумму для данного сочетания. Умножить на 120.

Вообще, можно хотя бы для случай 4 торговцев, 4 товаров и n=2 пример входных данных и результата? Для приведения понимания задачи всеми участниками к единому знаменателю.

[smishel]

Прикрепил табличку с примером поставщики - цены

[smishel]

Мы хотим выбрать 2-х торговцев, у которых закупить товары

[smishel]

До поиска минимума из 3-х, я как то не до пер. Это меняет всё!
Вопрос снят. Спасибо ГИГАНТСКОЕ!