БлогNot. Задача об ограниченном рюкзаке

Задача об ограниченном рюкзаке

В отличие от задачи о ранце 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

теги: числа c++ программирование

26.08.2020, 18:08; рейтинг: 59