Оптимизация перевозки грузов в лодке с одного берега на друг

[Fed]

Грузы различного вида (обозначим, как множество $X = \{x_1, x_2, ..., x_n\}$) необходимо перевезти с одного берега на другой, для чего используется лодка. Объем груза каждого вида (обозначим, как $V(x_i), i = 1:n$) строго меньше вместимости лодки $V$.
При перевозке грузы различного вида можно комбинировать только в заданных сочетаниях, т.е. в лодку могут быть помещены только заданные подмножества грузов множества $X$ (одноэлементные подмножества множества $X$ считаются априори заданными, остальные подмножества определяются в зависимости от вида грузов и текущих обстоятельств).
Каждому подмножеству множества $X$ поставлено в соответствие число, определяющее время перевозки с исходного берега на другой (на семействе множеств $X$ задана функция $F$). Время возврата лодки с противоположного берега на исходный является константой. Перевоз каждого груза по отдельности требует наименьшего количества времени, т.е. значение функции $F(х_1)$ всегда меньше или равно значению функции $F(\{x_1,x_2,x_3\}$). Но при этом $F(x_1)$ не обязательно может быть меньше, чем $F(\{x_2,x_3\}$).
Необходимо перевезти весь имеющийся груз на другой берег за минимальное время.
Груз каждого вида может делиться на части, т.е., если например, в лодку помещается груз $x_1$, а затем $x_2$, но для груза вида $x_2$ не хватает места, часть груза $x_2$ (или $x_1$) можно оставить до следующего раза (вопрос, также требующий разрешения, --- какой вид груза оставлять на берегу при перегрузе лодки.).

Не хотелось бы изобретать велосипед, а попытаться классифицировать приведенную выше задачу (а там сразу и метод (методы) решения обнаружится). Не удалось классифицировать приведенную задачу, как дискретную задачу о рюкзаке (о нескольких рюкзаках) или задачу о раскрое (хотя, аналогии ощущаются). Полной уверенности (доказательства) пока нет, но задача, кажется, NP-полная.
Имеющийся на данный момент метод решения задачи, позволяющий с уверенностью получить оптимальное решение, --- метод ветвей и границ (хотя, как кажется, применение метода ветвей и границ особенной эффективности по сравнению с полным перебором не даст, отсечение ветвей будет проводиться лишь на предпоследнем и последнем шаге). От метода в данном случае остается одно лишь красивое название, без ощутимой эффективности его применения.
Как здесь применить динамическое программирование (принцип Белмана) --- тоже пока не ясно.
Спасибо.

[Fed]

Рассмотрим известную задачу покрытия с минимальным весом. Задано множество X = \{x_1, x_2, ..., x_n\} и семейство его подмножеств S = \{s_1, s_2, ..., s_m\}. Определим на семействе S вещественную функцию c:S \rightarrow R^+. Необходимо найти такое покрытие C \subseteq S, \cup_{s \in C} \{s\} = X, что вес покрытия \sum\limits_{s \in C} c(s) минимален.
В данном случае:
X --- множество грузов,
S --- семейство его подмножеств (возможные комбинации одновременного перевоза нескольких грузов),
значение функции c(s'), s' \in S --- есть время перевозки для s'.

Если бы не ограничение на вместимость лодки, то на этом можно было бы завершить классификацию задачи, сказав, что она NP-трудная. Ограничение на вместимость требует (а вернее, может потребовать) разбиения элементов покрывающего подсемейства --- "комбинации" на "подкомбинации". К задаче нахождения покрытия с минимальным весом добавляется ограничение на вес элемента покрывающего подсемейства C. Спрашивается, остается ли после добавления упомянутого ограничения задача перевозки груза NP-трудной или нет? Скорее всего --- да, остается, но как это доказать, пока не знаю. Не нашел также подобного случая и в литературе.

Разбиение каждого из элементов подсемейства C также является NP-трудной задачей (известная задача разбиения множества чисел). Но я не уверен, что после "разбиения" элементов оптимального покрытия C, полученное в итоге решение будет оптимальным для задачи перевозки грузов.