I'm trying to solve the following problem in the most efficient way I can find.
I want to trade my items for someone elses items, every item have a price and a value.
I want to maximize the value of the items I trade, so for example:
Banana, P: 10, V: 5
Pen, P: 3, V: 1
Paper, P: 1, V: 1
Phone, P: 10, V: 8
Key, P: 1, V: 2
Wallet, P: 30, V: 100
You can see that I can trade my Banana and Paper (with value of 6) with Phone and Key (with value of 10)
I can overpay but can not pay less and the amount I overpay is lost.
Currently my solution is to use generate all the possible combinations of my items and try to match the price with knapsack algorithm and check each result.
This is however very not efficient because I can have over 1000 items (both mine and the other person).
Does anyone have a possible solution to this problem? I need it to be efficient but also give me the best solution (best value)
- The items are not infinite and they have a limit.