Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Backpack with recursion
//Title of this code //g++ 4.8.2 #include <iostream> #include <vector> #include <set> struct pair { int size; int value; pair(int s, int v): size(s), value(v) {} }; struct retType { std::vector<int> arr; int best; }; retType maxPack(std::vector<pair> t, int backSize, std::set<int> usedPos = {}) { int best = 0; int pos = -1; std::vector<int> array; retType retVal; for (int i = 0; i < t.size(); ++i) { int size = t[i].size; int value = t[i].value; if (usedPos.find(i) == usedPos.end() && backSize - size >= 0) { std::set<int> tmpUsedPos = usedPos; tmpUsedPos.insert(i); retType ret = maxPack(t, backSize - size, tmpUsedPos); if (ret.best + value > best) { best = ret.best + value; array = ret.arr; pos = i; } } } if (pos > -1) array.push_back(pos); retVal.arr = array; retVal.best = best; return retVal; } int main() { std::vector<pair> stuff = {pair(2,3), pair(1,4), pair(2,5), pair(4,6), pair(3,3)}; int packSize = 5; retType rv = maxPack(stuff, packSize); std::cout << rv.best << std::endl; for (int i = 0; i < rv.arr.size(); ++i) std::cout << rv.arr[i] << " "; }
run
|
edit
|
history
|
help
0
Stock buy/sell, maximum subarray problem
Policy based smart pointer
RegexSearch
HTML Node
Finding the first digit of a number
work
Continuous Sub Set with given sum
ExceptionHandling4
Pairs having sum equal to target
Function to m_function