algorithms

[sharangchopra]

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

[mutexe]

if there is no relation between price and rating then how can you devise an algorithm for what you want?

[sharangchopra]

what i meant was that dont assume that the product with higher rating will cost more

[sharangchopra]

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

[sharangchopra]

you will be given two arays

[coder777]

Make an array of structs like this:

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).

[sharangchopra]

this is surely incorrect

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

budget->65

check urself

[MiiNiPaa]

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.

[coder777]

Repeat the steps with all possible combinations (downward) until you have your maximum.

It is just an idea not the final solution.