Блог

Учитывая, что в файле данных указаны идентификатор магазина, стоимость, товары, какой алгоритм мне следует использовать, чтобы получить все запрошенные запасные части из одного магазина с минимальным выигрышем. Если не удается найти ни одного магазина, следует напечатать «None». Кроме того, нет ничего плохого в покупке дополнительных запасных частей за минимальный приз.

 Shop ID,    Cost($),    Items List
1,          4.00,       E
1,          8.00,       F
2,          5.00,       E
2,          6.50,       F
5,          4.00,       A
5,          8.00,       D
6,          5.00,       D
6,          6.00,       A, B, C  ; Here in 6$ three items can be obtained
7,          2.20,       B
7,          3.00,       B,C
7,          2.00,       B
7,          2.50,       C

a) Spare Parts : A,D

Output:
Shop ID-6 
Cost - 11.0$

b) Spare Parts : E,F

Output:
Shop ID-2 
Cost - 11.5$
  

Мой подход (который не работает):

a) Сначала получите общие идентификаторы магазинов для заданных входных данных

 shop_id_list=[]
for items in input_list:
    shop_id_list = getCommonShopIds(items.strip(), shop_id_list )
    all_items.append( items )
  

б) Для каждого all_items получите минимальную стоимость этого элемента во всех shop_id_list (0, если элементы уже включены в последнюю итерацию)

 res = [0 for x in range(len(shop_id_list)) ]
for items in all_items:
    all_cost = getMinShopCost( shop_id_list, items )
    res= map(operator.add, all_cost, res ) # Add those list
  

c) Найдите минимальный индекс элемента в res (скажем, i ) и выведите соответствующий shop_id_list[i] и res[i]

Моя логика не работает для таких случаев, как:

Ввод: B C

Он выводит 7 4.5 $

Ожидаемый показатель должен составлять 7 3,00 $

Является ли это какой-либо стандартной задачей или вариацией какой-либо задачи теории графов и т.д.?

Я не могу найти какой-либо оптимизированный подход, буду признателен за любую помощь.

^{PS: Python помечен только потому, что в вопросе есть фрагмент кода python, меня просто интересует подход. Кроме того, это не проблема с онлайн-конкурсом, о котором я не знаю.}

Здесь есть 2 шага.

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

Второй шаг: вам нужно рассчитать стоимость получения запчастей из каждого места в S. Вычисление стоимости для отдельного места является проблемой удовлетворения ограничений. http://en.wikipedia.org/wiki/Constraint_satisfaction_problem. Есть несколько способов, которыми вы могли бы решить эту проблему. Один из способов — использовать подход, основанный на смешанном целочисленном LP, со следующей формулировкой:

 Let X be the item groups bought
let y_1, .. y_n be the items you require

min F(X) = sum cost(X)
subject to:
y_i in X, for i in {1,..,n}
  

По сути, у вас есть некоторые бинарные ограничения. Скорее всего, есть лучшие способы сформулировать это, но, надеюсь, это даст вам общее представление.
Возможно, вы могли бы решить эту проблему с помощью какого-нибудь LP-решателя, такого как симплексный метод.

Если вы используете Python, взгляните на эти библиотеки решателей: http://www.scipy.org
https://software.sandia.gov//trac/coopr
https://code.google.com/p/pulp-or

После расчета затрат вы возвращаете место с наименьшей стоимостью из мест в S

Если проблема небольшая, то подойдет простое отслеживание назад :-

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

Кроме того, вы также можете предотвратить рекурсию, если стоимость уже превышает текущую минимальную стоимость.

Если количество предложений невелико, используйте также метод грубой силы :-

1. выберите подмножество предложений и отметьте все позиции, которые оно охватывает.
2. сгенерируйте из него n-разрядное число.
3. Поместите в хэш-карту n => минимальную стоимость.

Это очень эффективно, если у вас несколько заказов, так как тогда вам просто нужно выполнить поиск в хэш-карте, введя n-разрядный номер заказа.

Вы также можете попробовать метод ветвления и привязки с оценкой в виде суммы элементов, взятых по отдельности