Не смотря на решения, это выглядит как стандарт DP .
Каждое состояние представлено списком предметов, оставленных для покупки (2^15 комбинаций) и текущей позициейавтомобиля (50 хранит + 1 исходное положение = 51 возможные опции).
Переход из одного состояния в другое очень прост.
def minCost(itemsLeft, currentPosition)
current_minimum = INFINITY
for (each store in the list) {
if (store.containsSomeOf(itemsLeft)) {
candidate = minCost(itemsLeft - store.items, store)
+ cost_of_items_bought_at_store + cost_of_driving
current_minimum = min(current_minimum, candidate)
}
}
return current_minimum
end
Естественно, itemList представляется как битовая маска, а не как фактический список.
Вам также необходимо учитывать скоропортящиеся продукты, но это чисто технический вопрос.
Наконец, вам нужно либо применить памятка о рекурсии или перезаписи как чистого DP.