Почему собственно я пишу эту статью? На днях увидел интерестное задание, звучало оно примерно так. У вас есть n-ое количество предметов, которые имею название и вес каждый. И есть рюкзак (коробка, контейнер, как вам будет угодно) который вмещает определенное количество килограмм. Нужно найти оптимальный вариант помещения предметов в рюкзак, что бы вес положенных вещей был максимально приближенный к вместимости рюкзака (ну или, разумеется, забить его полностью). Это типичная задача «с рюкзаком», которая относится к классике оптимизации. Об этом вы уже могли читать на хабре вот тут. Но там более подробно описывается PuLP, а я хочу поставить акцент на исполнении алгоритма на языке С++.
Изначально, я понимал, что велосипед придумывать, мне явно не нужно. И тогда начал поиски похожих алгоритмов. Сначала нашел пример на английском Bin packing problem. Потом нашел русскоязычные варианты этой задачи, которые назывались .«Классическая задача с рюкзаком/ранцем».
И так, задания такого рода являются заданиями комбинаторной оптимизации. Хочу отметить что она является NP-задачей (псевдо-полиномиальна). Решена может быть динамисечким программированием или полным перебором. Мне подошло динамиское программирование ибо мне хватало одного оптимального варианта решения.
Релизация алгоритма Knapsack на С++:
Изначально, я понимал, что велосипед придумывать, мне явно не нужно. И тогда начал поиски похожих алгоритмов. Сначала нашел пример на английском Bin packing problem. Потом нашел русскоязычные варианты этой задачи, которые назывались .«Классическая задача с рюкзаком/ранцем».
И так, задания такого рода являются заданиями комбинаторной оптимизации. Хочу отметить что она является NP-задачей (псевдо-полиномиальна). Решена может быть динамисечким программированием или полным перебором. Мне подошло динамиское программирование ибо мне хватало одного оптимального варианта решения.
Релизация алгоритма Knapsack на С++:
int knapsack(const std::vector& wts, int W)
{
size_t n = wts.size();
std::vector<std::vector > dp(W + 1, std::vector(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] + wts[j-1]);
}
else
{
dp[w][j] = dp[w][j - 1];
}
}
}
return dp[W][n];
}
Как Вы видите, метод возвращает оптимальный вес, который может быть помещен в рюкзак.Отмечу, что код немного видоизмененный от стандартного, ибо параметр по которому сравнивать и вес у меня являются одним и тем же (value=weight).
Так же вот псевдокод, с помощью которого можем использовать елементы добавленные в рюкзак:
line <- W
i <- n
while (i> 0):
if dp[line][i] - dp[line][i-1] == value(i):
елемент 'i' помещен в рюкзаке
i <- i-1
else if dp[line][i] > dp[line][i-1]:
line <- line - 1
else:
i <- i-1
Вот собственно и всё. Прошу не судить строго, это первая моя писулинка на хабре, за которую надеюсь получить инвайт на данный сервис. Спасибо.