БлогNot. Непрерывная задача о рюкзаке

Непрерывная задача о рюкзаке

Непрерывная (Continuous или Fractional) задача о рюкзаке в отличие от задачи об ограниченном рюкзаке позоляет "резать" предметы на части, пропорционально снижая их стоимость (пол-батона колбасы стоит вдвое меньше целого), соответственно, исходные данные сразу задаются в вещественных числах.

Для каждого предмета известны вес и стоимость. Цель - набрать предметы так, чтобы общая стоимость рюкзака ограниченной вместимости была максимальной. В такой постановке задача становится очень проста и сводится к сортировке по убыванию соотношения "стоимость / вес", хотя с точки зрения производительности из-за необходимости сортировки такой алгоритм будет и не оптимальным.

Программа на консольном C++ проверялась Visual Studio 2019.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct item_type {
 string  name; //название
 double  weight, value; //вес, стоимость
};

vector <item_type> items;

int main() {
 //Название, вес, стоимость за кг
 items.push_back(item_type{ "Stuff 1", 30, 120 });
 items.push_back(item_type{ "Stuff 2", 20, 100});
 items.push_back(item_type{ "Stuff 3", 10, 60 });

 sort (
  begin(items), end(items), [](const item_type& a, const item_type& b) {
   return a.value / a.weight > b.value / b.weight;
 });

 double space = 50; //Ёмкость рюкзака в кг
 double finalvalue = 0.0;
 for (const auto& item : items) {
  if (space >= item.weight) {
   cout << "Take all " << item.name << endl;
   finalvalue += item.value;
  }
  else {
   cout << "Take " << space << " kg of " << item.name << endl;
   finalvalue += item.value * (space / item.weight);
   break;
  }

  space -= item.weight;
 }
 cout << "Total price = " << finalvalue;
 cin.get(); return 0;
}
Take all Stuff 3
Take all Stuff 2
Take 20 kg of Stuff 1
Total price = 240

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

26.08.2020, 18:51; рейтинг: 50