Или еще такой вариант: разбиваешь K (маршрут, или его длину) на какое-то количество небольших подмаршрутов, к примеру, 5, то есть длина каждого будет 5. Для каждого подмаршрута смотришь все его возможные комбинации перебором и выбираешь тот, который даст наибольшую сумму. У тебя задача при этом разобьется на более мелкие части.