dimanche 30 août 2020

Fractional knapsack problem : I'm unable to pass the 6th test case at Coursera .I'm getting more answer than the correct answer?

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