Задача об ограниченном рюкзаке
В отличие от задачи о ранце 0-1, в задаче об ограниченном рюкзаке каждый предмет может быть выбран не больше определённого количества раз. Исходные данные удобно задавать в виде таблицы с данными формата "предмет - вес - ценность (стоимость) - количество". Также задан предельный вес рюкзака в тех же единицах, что веса предметов.
Мы хотим наполнить рюкзак так, чтобы суммарная ценность выбранных предметов была максимальной. Предполагается, что все данные - целочисленные беззнаковые значения, код нетрудно модифицировать для вещественных чисел.
Тест в листинге - чисто "ловушечный", чтобы проверить "жадность" алгоритма (разница между весами велика, а по стоимости мала). Сработало верно, сунуть "самый дорогой" Stuff 1
не пытается. Программа на C++ проверялась в консоли Visual Studio 2019.
#include <iostream> #include <vector> #include <chrono> using namespace std; using namespace std::chrono; class StopTimer { //Таймер high_resolution_clock::time_point s; public: StopTimer() : s(high_resolution_clock::now()) {} unsigned long long getTime() const { duration< double > fs = high_resolution_clock::now() - s; milliseconds d = duration_cast<chrono::milliseconds>(fs); return d.count(); } }; struct KnapsackTask { //Рюкзак struct Item { //Предмет string name; unsigned w, v, qty; Item () : w(), v(), qty() {} Item(const string& iname, unsigned iw, unsigned iv, unsigned iqty) : name(iname), w(iw), v(iv), qty(iqty) {} }; typedef vector<Item> Items; struct Solution { //Решение unsigned v, w; unsigned long long iterations, usec; 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 logic_error("Bad 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 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 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 = 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(30); //Максимальный вес //Наименование - вес - ценность (стоимость) - количество task.add(Item("Stuff 1", 29, 100, 1)); task.add(Item("Stuff 2", 1, 99, 30)); task.add(Item("Stuff 4", 33, 10, 5)); } 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 << " ms" << 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; cin.get(); return 0; }
Iterations to solve: 33 Time to solve: 0 ms Solution: 30 Stuff 2 ( item weight = 1 ) Weight: 30 Value: 2970
26.08.2020, 18:08 [1159 просмотров]