имею следущее:- задача о рюкзаке (backpack/knapsack problem)
- bin packing problem
- задача о парламенте
- задача о назначениях
- задача о суммах подмножеств (subset-sum problem)
- задачи теории расписаний (задача Джонсона)
Но, разумеется, ни одна из выше указанных задач не подходит под определение "задачи о туристах". Есть сходства, конечно. На мой взгляд болше всех подходит задача о суммах подмножеств. Проблема в том , что задача решает проблему для лишь одного натурального числа, а необходимо решить задачу для n-чисел, при этом состовляя суммы подмножеств из одной и той же группы элементов.
Привожу решение для одного натурального числа:
| Цитата |
Задача о суммах подмножеств ("табличный" алгоритм) Пусть задана пара (S, t), где S = {x1, x2, …, xn} представляет собой множество положительных целых чисел, а t — положительное целое число. Требуется отыскать среди подмножеств множества S, сумма которых не превосходит t, такое, у которого сумма ближе всего к t. Пусть |S| = n. Обозначим (k, w) — задачу, в которой имеется k первых чисел из S и нужно набрать сумму w. Таким образом исходная задача — это задача (n, t). Для решения задачи построим таблицу T[n, t + 1], в клетку T[i, j] которой будем записывать оптимальное решение задачи (i, j). Первый столбец заполним нулями. Первую строку заполним сначала нулями, а начиная с клетки (1, x1) — числами x1. Клетку T[i, j] (i, j > 1) будем заполнять по правилу: Если j − xi > 0, то y := T[i − 1, j − xi], иначе y := 0; T[i, j] := max(T [i − 1, j], y + xi) \ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 3 0 0 0 3 3 3 3 3 3 3 3 3 3 3 5 0 0 0 3 3 5 5 5 8 8 8 8 8 8 7 0 0 0 3 3 5 5 7 8 8 10 10 12 12 9 0 0 0 3 3 5 5 7 8 9 10 10 12 12 11 0 0 0 3 3 5 5 7 8 9 10 11 12 12 S = {3, 5, 7, 9, 11} t = 13; Таблица примет такой вид. Ответ: нет подмножества весом 13, ближе всего снизу 12. Условие (2) говорит о том, что оптимальная сумма может достигаться либо без использования xi (T[i − 1, j]), либо если xi входит в сумму (y + xi). В этом случае его надо прибавить к решению задачи (i − 1, j − xi), что и сохраняется в переменной y в условии (1). Из получившейся таблицы можно узнать и состав оптимальной суммы. Трудоемкость этого алгоритма очевидно составляет O (nt) операций. Таким образом, если t будет велико, можно будет все числа поделить, к примеру, на 10, округлить и получить приближенный алгоритм. |
пытаясь заснуть я все таки пришел к тому, что это, дейсвительно, проблема о рюкзаке, точнее о рюкзаках.