Какой выбрать алгоритм для решения задачи?
Так вроде это классическая задача коммивояжера. В википедии описаны алгоритмы решения этой задачи. Проанализируй все и выбери оптимальный.
Если есть память N*2^N, где N - число городов, то можно воспользоваться динамикой по набору пройденных городов плюс последнему городу, где оказался коммивояжер. Для каждого такого сочетания запоминаем минимальное количество топлива, которое потребовалось, чтобы добраться до этой ситуации и город, из которого приехали в последний город. Потом для всех ситуаций проезжаем из последнего города по всем рёбрам, и попадаем в ситуации, где посещённых городов на 1 больше. Снова для каждой находим оптимальный (по топливу) путь, по которому мы туда попали... и так, пока топливо не кончится. После чего проходимся по всему списку, и смотрим, где больше собрано призов.
До 20-25 городов должно работать разумное время. Дальше придётся искать эвристики.