Непрерывная задача о рюкзаке
Непрерывная (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
26.08.2020, 18:51 [1393 просмотра]