algorithms

Jul 8, 2015 at 10:29am

The problem is that I have n products each product has a price and a rating(there is no relation between price and rating)and have a budget say K.I have to buy products such that the sum of rating is maximum and it does not exceed the budget.Each product can be bought only once.

Is there any well known algorithm for it ?

thanks
Jul 8, 2015 at 10:48am
if there is no relation between price and rating then how can you devise an algorithm for what you want?
Last edited on Jul 8, 2015 at 10:52am
Jul 8, 2015 at 11:04am
what i meant was that dont assume that the product with higher rating will cost more
Jul 8, 2015 at 11:09am
example
product ratings--> 46 78 12 72 90 11
product price ---> 10 13 7 12 15 8
budget--> 20

so the answer should be 78+12


Jul 8, 2015 at 11:10am
you will be given two arays
Jul 8, 2015 at 11:11am
Make an array of structs like this:
1
2
3
4
5
6
struct product
{
....
  double rating;
  double price;
};

Then oder the array according to the rating and then add the product to your final list until the budget is exhausted (actually subtract the price).
Jul 8, 2015 at 11:15am
this is surely incorrect

example
ratings--> 90 88 78 50
price --> 61 23 30 12

budget->65

check urself
Jul 8, 2015 at 11:33am
This is a classic Knapsack Problem: https://en.wikipedia.org/wiki/Knapsack_problem

There is no perfect solution which works in reasonable amount of time. Look at the link to see possible approximations.

Also if there is not many entries, use brute force: generate all possible combinations and choose best one.
Jul 8, 2015 at 11:38am
Repeat the steps with all possible combinations (downward) until you have your maximum.

It is just an idea not the final solution.
Topic archived. No new replies allowed.