Алфавитный алгоритм обнаружения объектов
Существует простое дп решение этой проблемы:
#include <vector>
#include <limits>
int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
size_t n = wts.size();
std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n+1, 0));
for (size_t j = 1; j <= n; j++) {
for (int w = 1; w <= W; w++) {
if (wts[j-1] <= w) {
dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
}
else {
dp[w][j] = dp[w][j - 1];
}
}
}
return dp[W][n];
}
Но как я могу узнать, какие предметы были взяты?
Решение
Сделайте второй вектор «prev» с теми же размерами, что и dp.
Когда вы выбираете лучший вариант для dp [w] [j], запишите координаты предыдущей ячейки в prev [w] [j]
Когда задание dp выполнено, вернитесь из prev [W] [n] назад, чтобы получить все используемые индексы ячеек.
Другие решения
Вы можете использовать карту, и как только объект будет создан, вы сможете сделать запрос, используя карту. Алгоритм оптимизации будет достигнут с использованием HashMap.
Основной проблемой вашего подхода является отсутствие кодирования концепции предмета как сущности. Вы должны создать тип «элемент» (используя class или же struct ключевое слово) для описания элемента с весом, стоимостью и каким-либо идентификатором (именем или номером) в качестве членов. Таким образом, вам нужно всего лишь отправить один вектор элементов, и любое решение будет представлять собой список таких элементов, который отвечает на ваш вопрос.
редактировать
За запросом следует более практическое объяснение того, как наивно заставить это работать.
Создать тип, item который содержит всю информацию об одном предмете. Принять std::vector<item> в качестве входа для замены обоих wts а также cost Тогда наименьшее возможное изменение состоит в том, чтобы изменить dp так что он хранит пары, состоящие из эксплуатационных расходов и списка товаров. Это даст ему тип std::vector<std::vector<std::pair<int,std::vector<item>>>>, То есть для каждого хранимого (частичного) решения следите за его стоимостью и элементами, дающими это решение.
Этот тип для dp выглядит довольно отвратительно, но если у вас все получится, вы сможете улучшить реализацию позже. Например, вы можете хранить указатели на itemс, чтобы избежать копирования. Также несколько typedefможет действительно помочь уточнить определение dp.. Важно сначала заставить его работать с самым простым решением, а затем подумать об этих улучшениях.