This is a C++ Program to solve fractional knapsack. The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
double bag( double w, vector<double> values,vector<double> weights, vector<double> vv){
double index, ma;
double W1=0.0;
double V=0.0;
while(!values.empty())
{
ma=*max_element(vv.begin(), vv.end()) ;
auto it = find(vv.begin(), vv.end(), ma);
index = distance(vv.begin(),it);
//cout<<index<<endl;
if(w-W1>=weights[index] )
{
V=V+values[index];
W1=W1+weights[index];
}
else if(w-W1<weights[index]&&w-W1>0)
{
V=V+vv[index]*(w-W1);
}
weights.erase(std::next(weights.begin(), std::distance(vv.begin(), it)));
values.erase(std::next(values.begin(), std::distance(vv.begin(), it)));
vv.erase(it);
}
return V;
}
int main() {
int n;
double w;
double ans;
std::cin >> n >> w;
vector<double> values(n);
vector<double> weights(n);
vector<double> vv(n);
for (int i = 0; i < n; i++) {
std::cin >> values[i] >> weights[i];
vv[i]=values[i]/weights[i];
}
ans = bag(w,values,weights,vv);
cout<<ans;
}
Aucun commentaire:
Enregistrer un commentaire