knapsack problem

Hello I found this code on a website (https://tfetimes.com/bounded-knapsack-problem/) is it possible to transform the weight limit and the weight of each object into comma numbers rather than whole numbers? Thank you

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225`` ``````#include #include #include #include #include #include using std::cout; using std::endl; class StopTimer { public: StopTimer(): begin_(getUsec()) {} unsigned long long getTime() const { return getUsec() - begin_; } private: static unsigned long long getUsec() { //...you might want to use something else under Windows timeval tv; const int res = ::gettimeofday( & tv, 0); if (res) return 0; return tv.tv_usec + 1000000 * tv.tv_sec; } unsigned long long begin_; }; struct KnapsackTask { struct Item { std::string name; unsigned w, v, qty; Item(): w(), v(), qty() {} Item(const std::string & iname, unsigned iw, unsigned iv, unsigned iqty): name(iname), w(iw), v(iv), qty(iqty) {} }; typedef std::vector < Item > Items; struct Solution { unsigned v, w; unsigned long long iterations, usec; std::vector < unsigned > n; Solution(): v(), w(), iterations(), usec() {} }; //... KnapsackTask(): maxWeight_(), totalWeight_() {} void add(const Item & item) { const unsigned totalItemWeight = item.w * item.qty; if (const bool invalidItem = !totalItemWeight) throw std::logic_error("Invalid item: " + item.name); totalWeight_ += totalItemWeight; items_.push_back(item); } const Items & getItems() const { return items_; } void setMaxWeight(unsigned maxWeight) { maxWeight_ = maxWeight; } unsigned getMaxWeight() const { return std::min(totalWeight_, maxWeight_); } private: unsigned maxWeight_, totalWeight_; Items items_; }; class BoundedKnapsackRecursiveSolver { public: typedef KnapsackTask Task; typedef Task::Item Item; typedef Task::Items Items; typedef Task::Solution Solution; void solve(const Task & task) { Impl(task, solution_).solve(); } const Solution & getSolution() const { return solution_; } private: class Impl { struct Candidate { unsigned v, n; bool visited; Candidate(): v(), n(), visited(false) {} }; typedef std::vector < Candidate > Cache; public: Impl(const Task & task, Solution & solution): items_(task.getItems()), maxWeight_(task.getMaxWeight()), maxColumnIndex_(task.getItems().size() - 1), solution_(solution), cache_(task.getMaxWeight() * task.getItems().size()), iterations_(0) {} void solve() { if (const bool nothingToSolve = !maxWeight_ || items_.empty()) return; StopTimer timer; Candidate candidate; solve(candidate, maxWeight_, items_.size() - 1); convertToSolution(candidate); solution_.usec = timer.getTime(); } private: void solve(Candidate & current, unsigned reminderWeight, const unsigned itemIndex) { ++iterations_; const Item & item(items_[itemIndex]); if (const bool firstColumn = !itemIndex) { const unsigned maxQty = std::min(item.qty, reminderWeight / item.w); current.v = item.v * maxQty; current.n = maxQty; current.visited = true; } else { const unsigned nextItemIndex = itemIndex - 1; { Candidate & nextItem = cachedItem(reminderWeight, nextItemIndex); if (!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); current.visited = true; current.v = nextItem.v; current.n = 0; } if (reminderWeight >= item.w) { for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems) { reminderWeight -= item.w; Candidate & nextItem = cachedItem(reminderWeight, nextItemIndex); if (!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); const unsigned checkValue = nextItem.v + numberOfItems * item.v; if (checkValue > current.v) { current.v = checkValue; current.n = numberOfItems; } if (!(reminderWeight >= item.w)) break; } } } } void convertToSolution(const Candidate & candidate) { solution_.iterations = iterations_; solution_.v = candidate.v; solution_.n.resize(items_.size()); const Candidate * iter = & candidate; unsigned weight = maxWeight_, itemIndex = items_.size() - 1; while (true) { const unsigned currentWeight = iter -> n * items_[itemIndex].w; solution_.n[itemIndex] = iter -> n; weight -= currentWeight; if (!itemIndex--) break; iter = & cachedItem(weight, itemIndex); } solution_.w = maxWeight_ - weight; } Candidate & cachedItem(unsigned weight, unsigned itemIndex) { return cache_[weight * maxColumnIndex_ + itemIndex]; } const Items & items_; const unsigned maxWeight_; const unsigned maxColumnIndex_; Solution & solution_; Cache cache_; unsigned long long iterations_; }; Solution solution_; }; void populateDataset(KnapsackTask & task) { typedef KnapsackTask::Item Item; task.setMaxWeight(400); task.add(Item("map", 9, 150, 1)); task.add(Item("compass", 13, 35, 1)); task.add(Item("water", 153, 200, 2)); task.add(Item("sandwich", 50, 60, 2)); task.add(Item("glucose", 15, 60, 2)); task.add(Item("tin", 68, 45, 3)); task.add(Item("banana", 27, 60, 3)); task.add(Item("apple", 39, 40, 3)); task.add(Item("cheese", 23, 30, 1)); task.add(Item("beer", 52, 10, 3)); task.add(Item("suntancream", 11, 70, 1)); task.add(Item("camera", 32, 30, 1)); task.add(Item("T-shirt", 24, 15, 2)); task.add(Item("trousers", 48, 10, 2)); task.add(Item("umbrella", 73, 40, 1)); task.add(Item("w-trousers", 42, 70, 1)); task.add(Item("w-overclothes", 43, 75, 1)); task.add(Item("note-case", 22, 80, 1)); task.add(Item("sunglasses", 7, 20, 1)); task.add(Item("towel", 18, 12, 2)); task.add(Item("socks", 4, 50, 1)); task.add(Item("book", 30, 10, 2)); } int main() { KnapsackTask task; populateDataset(task); BoundedKnapsackRecursiveSolver solver; solver.solve(task); const KnapsackTask::Solution & solution = solver.getSolution(); cout << "Iterations to solve: " << solution.iterations << endl; cout << "Time to solve: " << solution.usec << " usec" << endl; cout << "Solution:" << endl; for (unsigned i = 0; i < solution.n.size(); ++i) { if (const bool itemIsNotInKnapsack = !solution.n[i]) continue; cout << " " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl; } cout << "Weight: " << solution.w << " Value: " << solution.v << endl; return 0; }``````
Last edited on
do you mean 3.14159 or 3,14159 (, and . change depending on country)?
if so,
double type is what you want:
eg line 68 replace unsigned with double, but you will have to fix it everywhere that applies to weight.
Like this ?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237`` ``````#include #include #include #include #include #include using std::cout; using std::endl; class StopTimer { public: StopTimer(): begin_(getUsec()) {} unsigned long long getTime() const { return getUsec() - begin_; } private: static unsigned long long getUsec() {//...you might want to use something else under Windows timeval tv; const int res = ::gettimeofday(&tv, 0); if(res) return 0; return tv.tv_usec + 1000000 * tv.tv_sec; } unsigned long long begin_; }; struct KnapsackTask { struct Item { std::string name; unsigned v; double w, qty; Item(): w(), v(), qty() {} Item(const std::string& iname, double iw, unsigned iv, double iqty): name(iname), w(iw), v(iv), qty(iqty) {} }; typedef std::vector Items; struct Solution { unsigned v, w; unsigned long long iterations, usec; std::vector n; Solution(): v(), w(), iterations(), usec() {} }; //... KnapsackTask(): maxWeight_(), totalWeight_() {} void add(const Item& item) { double totalItemWeight = item.w * item.qty; if(const bool invalidItem = !totalItemWeight) throw std::logic_error("Invalid item: " + item.name); totalWeight_ += totalItemWeight; items_.push_back(item); } const Items& getItems() const { return items_; } void setMaxWeight(double maxWeight) { maxWeight_ = maxWeight; } double getMaxWeight() const { return std::min(totalWeight_, maxWeight_); } private: double maxWeight_, totalWeight_; Items items_; }; class BoundedKnapsackRecursiveSolver { public: typedef KnapsackTask Task; typedef Task::Item Item; typedef Task::Items Items; typedef Task::Solution Solution; void solve(const Task& task) { Impl(task, solution_).solve(); } const Solution& getSolution() const { return solution_; } private: class Impl { struct Candidate { unsigned v, n; bool visited; Candidate(): v(), n(), visited(false) {} }; typedef std::vector Cache; public: Impl(const Task& task, Solution& solution): items_(task.getItems()), maxWeight_(task.getMaxWeight()), maxColumnIndex_(task.getItems().size() - 1), solution_(solution), cache_(task.getMaxWeight() * task.getItems().size()), iterations_(0) {} void solve() { if(const bool nothingToSolve = !maxWeight_ || items_.empty()) return; StopTimer timer; Candidate candidate; solve(candidate, maxWeight_, items_.size() - 1); convertToSolution(candidate); solution_.usec = timer.getTime(); } private: void solve(Candidate& current, double reminderWeight, const unsigned itemIndex) { ++iterations_; const Item& item(items_[itemIndex]); if(const bool firstColumn = !itemIndex) { double maxQty = std::min(item.qty, reminderWeight/item.w); current.v = item.v * maxQty; current.n = maxQty; current.visited = true; } else { const unsigned nextItemIndex = itemIndex - 1; { Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex); if(!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); current.visited = true; current.v = nextItem.v; current.n = 0; } if(reminderWeight >= item.w) { for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems) { reminderWeight -= item.w; Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex); if(!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); const unsigned checkValue = nextItem.v + numberOfItems * item.v; if ( checkValue > current.v) { current.v = checkValue; current.n = numberOfItems; } if(!(reminderWeight >= item.w)) break; } } } } void convertToSolution(const Candidate& candidate) { solution_.iterations = iterations_; solution_.v = candidate.v; solution_.n.resize(items_.size()); const Candidate* iter = &candidate; unsigned weight = maxWeight_, itemIndex = items_.size() - 1; while(true) { const unsigned currentWeight = iter->n * items_[itemIndex].w; solution_.n[itemIndex] = iter->n; weight -= currentWeight; if(!itemIndex--) break; iter = &cachedItem(weight, itemIndex); } solution_.w = maxWeight_ - weight; } Candidate& cachedItem(unsigned weight, unsigned itemIndex) { return cache_[weight * maxColumnIndex_ + itemIndex]; } const Items& items_; const unsigned maxWeight_; const unsigned maxColumnIndex_; Solution& solution_; Cache cache_; unsigned long long iterations_; }; Solution solution_; }; void populateDataset(KnapsackTask& task) { typedef KnapsackTask::Item Item; task.setMaxWeight( 400 ); task.add(Item("map",9.20,150,1)); task.add(Item("compass",13.10,35,1)); task.add(Item("water",153.50,200,2)); task.add(Item("sandwich",50,60,2)); task.add(Item("glucose",15,60,2)); task.add(Item("tin",68,45,3)); task.add(Item("banana",27,60,3)); task.add(Item("apple",39,40,3)); task.add(Item("cheese",23,30,1)); task.add(Item("beer",52,10,3)); task.add(Item("suntancream",11,70,1)); task.add(Item("camera",32,30,1)); task.add(Item("T-shirt",24,15,2)); task.add(Item("trousers",48,10,2)); task.add(Item("umbrella",73,40,1)); task.add(Item("w-trousers",42,70,1)); task.add(Item("w-overclothes",43,75,1)); task.add(Item("note-case",22,80,1)); task.add(Item("sunglasses",7,20,1)); task.add(Item("towel",18,12,2)); task.add(Item("socks",4,50,1)); task.add(Item("book",30,10,2)); } int main() { KnapsackTask task; populateDataset(task); BoundedKnapsackRecursiveSolver solver; solver.solve(task); const KnapsackTask::Solution& solution = solver.getSolution(); cout << "Iterations to solve: " << solution.iterations << endl; cout << "Time to solve: " << solution.usec << " usec" << endl; cout << "Solution:" << endl; for (unsigned i = 0; i < solution.n.size(); ++i) { if (const bool itemIsNotInKnapsack = !solution.n[i]) continue; cout << " " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl; } cout << "Weight: " << solution.w << " Value: " << solution.v << endl; return 0; }``````
@162, 165, 179 ... you need to go back over this.
Last edited on
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237`` ``````#include #include #include #include #include #include using std::cout; using std::endl; class StopTimer { public: StopTimer(): begin_(getUsec()) {} unsigned long long getTime() const { return getUsec() - begin_; } private: static unsigned long long getUsec() {//...you might want to use something else under Windows timeval tv; const int res = ::gettimeofday(&tv, 0); if(res) return 0; return tv.tv_usec + 1000000 * tv.tv_sec; } unsigned long long begin_; }; struct KnapsackTask { struct Item { std::string name; unsigned v; double w, qty; Item(): w(), v(), qty() {} Item(const std::string& iname, double iw, unsigned iv, double iqty): name(iname), w(iw), v(iv), qty(iqty) {} }; typedef std::vector Items; struct Solution { unsigned v, w; unsigned long long iterations, usec; std::vector n; Solution(): v(), w(), iterations(), usec() {} }; //... KnapsackTask(): maxWeight_(), totalWeight_() {} void add(const Item& item) { double totalItemWeight = item.w * item.qty; if(const bool invalidItem = !totalItemWeight) throw std::logic_error("Invalid item: " + item.name); totalWeight_ += totalItemWeight; items_.push_back(item); } const Items& getItems() const { return items_; } void setMaxWeight(double maxWeight) { maxWeight_ = maxWeight; } double getMaxWeight() const { return std::min(totalWeight_, maxWeight_); } private: double maxWeight_, totalWeight_; Items items_; }; class BoundedKnapsackRecursiveSolver { public: typedef KnapsackTask Task; typedef Task::Item Item; typedef Task::Items Items; typedef Task::Solution Solution; void solve(const Task& task) { Impl(task, solution_).solve(); } const Solution& getSolution() const { return solution_; } private: class Impl { struct Candidate { unsigned v, n; bool visited; Candidate(): v(), n(), visited(false) {} }; typedef std::vector Cache; public: Impl(const Task& task, Solution& solution): items_(task.getItems()), maxWeight_(task.getMaxWeight()), maxColumnIndex_(task.getItems().size() - 1), solution_(solution), cache_(task.getMaxWeight() * task.getItems().size()), iterations_(0) {} void solve() { if(const bool nothingToSolve = !maxWeight_ || items_.empty()) return; StopTimer timer; Candidate candidate; solve(candidate, maxWeight_, items_.size() - 1); convertToSolution(candidate); solution_.usec = timer.getTime(); } private: void solve(Candidate& current, double reminderWeight, const unsigned itemIndex) { ++iterations_; const Item& item(items_[itemIndex]); if(const bool firstColumn = !itemIndex) { double maxQty = std::min(item.qty, reminderWeight/item.w); current.v = item.v * maxQty; current.n = maxQty; current.visited = true; } else { const unsigned nextItemIndex = itemIndex - 1; { Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex); if(!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); current.visited = true; current.v = nextItem.v; current.n = 0; } if(reminderWeight >= item.w) { for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems) { reminderWeight -= item.w; Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex); if(!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); const unsigned checkValue = nextItem.v + numberOfItems * item.v; if ( checkValue > current.v) { current.v = checkValue; current.n = numberOfItems; } if(!(reminderWeight >= item.w)) break; } } } } void convertToSolution(const Candidate& candidate) { solution_.iterations = iterations_; solution_.v = candidate.v; solution_.n.resize(items_.size()); const Candidate* iter = &candidate; double weight = maxWeight_, itemIndex = items_.size() - 1; while(true) { double currentWeight = iter->n * items_[itemIndex].w; solution_.n[itemIndex] = iter->n; weight -= currentWeight; if(!itemIndex--) break; iter = &cachedItem(weight, itemIndex); } solution_.w = maxWeight_ - weight; } Candidate& cachedItem(unsigned weight, unsigned itemIndex) { return cache_[weight * maxColumnIndex_ + itemIndex]; } const Items& items_; double maxWeight_; const unsigned maxColumnIndex_; Solution& solution_; Cache cache_; unsigned long long iterations_; }; Solution solution_; }; void populateDataset(KnapsackTask& task) { typedef KnapsackTask::Item Item; task.setMaxWeight( 450.60 ); task.add(Item("map",9.20,150,1)); task.add(Item("compass",13.10,35,1)); task.add(Item("water",153.50,200,2)); task.add(Item("sandwich",50.2,60,2)); task.add(Item("glucose",15.1,60,2)); task.add(Item("tin",68.3,45,3)); task.add(Item("banana",27.1,60,3)); task.add(Item("apple",39.2,40,3)); task.add(Item("cheese",23.1,30,1)); task.add(Item("beer",52.5,10,3)); task.add(Item("suntancream",11.3,70,1)); task.add(Item("camera",32.1,30,1)); task.add(Item("T-shirt",24.1,15,2)); task.add(Item("trousers",48.2,10,2)); task.add(Item("umbrella",73.3,40,1)); task.add(Item("w-trousers",42.1,70,1)); task.add(Item("w-overclothes",43.5,75,1)); task.add(Item("note-case",22.2,80,1)); task.add(Item("sunglasses",7.1,20,1)); task.add(Item("towel",18.9,12,2)); task.add(Item("socks",4.4,50,1)); task.add(Item("book",30.2,10,2)); } int main() { KnapsackTask task; populateDataset(task); BoundedKnapsackRecursiveSolver solver; solver.solve(task); const KnapsackTask::Solution& solution = solver.getSolution(); cout << "Iterations to solve: " << solution.iterations << endl; cout << "Time to solve: " << solution.usec << " usec" << endl; cout << "Solution:" << endl; for (unsigned i = 0; i < solution.n.size(); ++i) { if (const bool itemIsNotInKnapsack = !solution.n[i]) continue; cout << " " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl; } cout << "Weight: " << solution.w << " Value: " << solution.v << endl; return 0; }``````

It's good, like this ?
43? 174?

Do you have grep? Or some other search tool? Just look through the code for the weight variables and where they are defined... those are the last 2 I see, but I just did it by hand.

this is very crude and rather old but if you don't have grep you can try it to search terms. It accepts multiple terms, eg whatever.exe filename.cpp w weight (see the problem with a variable name like w? its hard to isolate, you can put "w " or ".w " but wouldnt it be nice if it were called weight or mass or something distinct?)

 ``1234567891011121314151617`` ``````int main(int argc, char**argv) { ifstream ifs(argv[1]); char line[10000]; bool in{}; int ctr{}; uint64_t i; while(ifs.getline(line,10000)) { ++ctr; in = false; for(i = 2; i < argc; i++) in |= (bool)(strstr(line,argv[i])); if(in) cout <

Last edited on
Hello, sorry I didn't have time to get back to it, like this is good?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213`` ``````#include #include #include #include #include #include using std::cout; using std::endl; class StopTimer { public: StopTimer() : begin_(getUsec()) {} unsigned long long getTime() const { return getUsec() - begin_; } private: static unsigned long long getUsec() { //...you might want to use something else under Windows timeval tv; const int res = ::gettimeofday(&tv, 0); if (res) return 0; return tv.tv_usec + 1000000 * tv.tv_sec; } unsigned long long begin_; }; struct KnapsackTask { struct Item { std::string name; unsigned v; double mass, qty; Item() : mass(), v(), qty() {} Item(const std::string& iname, double iw, unsigned iv, double iqty) : name(iname), mass(iw), v(iv), qty(iqty) {} }; typedef std::vector Items; struct Solution { unsigned v; double mass; unsigned long long iterations, usec; std::vector n; Solution() : v(), mass(), iterations(), usec() {} }; //... KnapsackTask() : maxWeight_(), totalWeight_() {} void add(const Item& item) { double totalItemWeight = item.mass * item.qty; if (const bool invalidItem = !totalItemWeight) throw std::logic_error("Invalid item: " + item.name); totalWeight_ += totalItemWeight; items_.push_back(item); } const Items& getItems() const { return items_; } void setMaxWeight(double maxWeight) { maxWeight_ = maxWeight; } double getMaxWeight() const { return std::min(totalWeight_, maxWeight_); } private: double maxWeight_, totalWeight_; Items items_; }; class BoundedKnapsackRecursiveSolver { public: typedef KnapsackTask Task; typedef Task::Item Item; typedef Task::Items Items; typedef Task::Solution Solution; void solve(const Task& task) { Impl(task, solution_).solve(); } const Solution& getSolution() const { return solution_; } private: class Impl { struct Candidate { unsigned v, n; bool visited; Candidate() : v(), n(), visited(false) {} }; typedef std::vector Cache; public: Impl(const Task& task, Solution& solution) : items_(task.getItems()), maxWeight_(task.getMaxWeight()), maxColumnIndex_(task.getItems().size() - 1), solution_(solution), cache_(task.getMaxWeight() * task.getItems().size()), iterations_(0) {} void solve() { if (const bool nothingToSolve = !maxWeight_ || items_.empty()) return; StopTimer timer; Candidate candidate; solve(candidate, maxWeight_, items_.size() - 1); convertToSolution(candidate); solution_.usec = timer.getTime(); } private: void solve(Candidate& current, double reminderWeight, const unsigned itemIndex) { ++iterations_; const Item& item(items_[itemIndex]); if (const bool firstColumn = !itemIndex) { double maxQty = std::min(item.qty, reminderWeight / item.mass); current.v = item.v * maxQty; current.n = maxQty; current.visited = true; } else { const unsigned nextItemIndex = itemIndex - 1; { Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex); if (!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); current.visited = true; current.v = nextItem.v; current.n = 0; } if (reminderWeight >= item.mass) { for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems) { reminderWeight -= item.mass; Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex); if (!nextItem.visited) solve(nextItem, reminderWeight, nextItemIndex); const unsigned checkValue = nextItem.v + numberOfItems * item.v; if (checkValue > current.v) { current.v = checkValue; current.n = numberOfItems; } if (!(reminderWeight >= item.mass)) break; } } } } void convertToSolution(const Candidate& candidate) { solution_.iterations = iterations_; solution_.v = candidate.v; solution_.n.resize(items_.size()); const Candidate* iter = &candidate; double weight = maxWeight_, itemIndex = items_.size() - 1; while (true) { double currentWeight = iter->n * items_[itemIndex].mass; solution_.n[itemIndex] = iter->n; weight -= currentWeight; if (!itemIndex--) break; iter = &cachedItem(weight, itemIndex); } solution_.mass = maxWeight_ - weight; } Candidate& cachedItem(double weight, unsigned itemIndex) { return cache_[weight * maxColumnIndex_ + itemIndex]; } const Items& items_; double maxWeight_; const unsigned maxColumnIndex_; Solution& solution_; Cache cache_; unsigned long long iterations_; }; Solution solution_; }; void populateDataset(KnapsackTask& task) { typedef KnapsackTask::Item Item; task.setMaxWeight(450.60); task.add(Item("map", 9.20, 150, 1)); task.add(Item("compass", 13.10, 35, 1)); task.add(Item("water", 153.50, 200, 2)); task.add(Item("sandwich", 50.2, 60, 2)); task.add(Item("glucose", 15.1, 60, 2)); task.add(Item("tin", 68.3, 45, 3)); task.add(Item("banana", 27.1, 60, 3)); task.add(Item("apple", 39.2, 40, 3)); task.add(Item("cheese", 23.1, 30, 1)); task.add(Item("beer", 52.5, 10, 3)); task.add(Item("suntancream", 11.3, 70, 1)); task.add(Item("camera", 32.1, 30, 1)); task.add(Item("T-shirt", 24.1, 15, 2)); task.add(Item("trousers", 48.2, 10, 2)); task.add(Item("umbrella", 73.3, 40, 1)); task.add(Item("w-trousers", 42.1, 70, 1)); task.add(Item("w-overclothes", 43.5, 75, 1)); task.add(Item("note-case", 22.2, 80, 1)); task.add(Item("sunglasses", 7.1, 20, 1)); task.add(Item("towel", 18.9, 12, 2)); task.add(Item("socks", 4.4, 50, 1)); task.add(Item("book", 30.2, 10, 2)); } int main() { KnapsackTask task; populateDataset(task); BoundedKnapsackRecursiveSolver solver; solver.solve(task); const KnapsackTask::Solution& solution = solver.getSolution(); cout << "Iterations to solve: " << solution.iterations << endl; cout << "Time to solve: " << solution.usec << " usec" << endl; cout << "Solution:" << endl; for (unsigned i = 0; i < solution.n.size(); ++i) { if (const bool itemIsNotInKnapsack = !solution.n[i]) continue; cout << " " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].mass << " )" << endl; } cout << "Weight: " << solution.mass << " Value: " << solution.v << endl; return 0; }``````