Рекурсивный возврат, показывающий лучшее решение

В школе я должен использовать рекурсивное отслеживание, чтобы решить головоломку с лодкой. Пользователь вводит максимальный вес для лодки, количество типов предметов, а также вес и значение для каждого типа предметов. На лодке можно разместить более одного предмета каждого типа.

Наше задание гласит: «Программа должна найти решение, которое наполняет лодку выбранными ценными предметами так, чтобы общая стоимость предметов в лодке была максимальной, а общий вес предметов оставался в пределах грузоподъемности лодки».

У этого также есть довольно определенный шаблон для алгоритма рекурсивного возврата.

В настоящее время я использую смежные списки предметов для хранения возможных предметов и предметов на лодке. Структура элемента включает в себя члены типа int для веса, значения, количества (от того, сколько раз он используется) и уникальный код для печати. Затем у меня есть класс Boat, который содержит элементы данных max_weight, current_weight, value_sum и члены для каждого из смежных списков, а затем функции-члены, необходимые для решения головоломки. Кажется, что все мои функции класса работают отлично, и моя рекурсия действительно отображает правильный ответ с учетом примера ввода.

То, что я не могу понять, это условие для дополнительного кредита, а именно: «Измените вашу программу так, чтобы она отображала лучшее решение с наименьшим общим весом. Если есть два решения с одинаковым общим весом, разбейте связать, выбрав решение с наименьшим количеством элементов в нем. » Я смотрел на это некоторое время, но я просто не уверен, как я могу изменить его, чтобы убедиться, что вес минимизирован, а также максимизируется значение. Вот код для моего решения:

bool solve(Boat &boat) {
if (boat.no_more()) {
boat.print();
return true;
}
else {
int pos;
for (int i = 0; i < boat.size(); i++){
if (boat.can_place(i)) {
pos = boat.add_item(i);
bool solved = solve(boat);
boat.remove_item(pos);
if (solved) return true;
}

}
return false;
}
}

Все функции в точности соответствуют их названию. Больше не возвращает true, если ни один из возможных предметов не поместится на лодке. Размер возвращает размер списка возможных элементов. Добавление и удаление элементов изменяет данные количества элементов, а также членов Boat current_weight и value_sum соответственно. Также параметр add_item, remove_item и can_place является индексом возможного элемента, который используется. Чтобы убедиться, что найдено максимальное значение, список возможных элементов отсортирован в порядке убывания по значению в конструкторе Boat, который принимает список возможных элементов в качестве параметра.

Также вот пример того, как выглядит ввод и вывод:

Любое понимание очень ценится!