Решение задачи о рюкзаке методом исчерпывающего перебора - EcsFlash/DataTypes GitHub Wiki
Дано n предметов весом и ценной, а также рюкзак, выдерживающий вес W. Требуется найти подмножество предметов, которое можно разместить в рюкзаке, и которое имеет при этом максимальную стоимость.
//weight - текущий вес
//cost - стоимость взятого в рюкзак
//index - позиция элемента в массиве, подлежащего к рассмотрению на попадание в рюкзак
int backpack(int index,int W, int n, vector<pair<int, int>> obj,int weight,int cost)
{
if (weight > W)
return 0;
if (index == n)
return cost;
int take;
if (weight + obj[index].first <= W)
{
take = backpack(index + 1, W, n, obj, weight + obj[index].first, cost + obj[index].second);
}
int skip = backpack(index + 1, W, n, obj, weight, cost);
return max(take, skip);
}