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.
I don't really have a scale how much efficient it need to be I need it for a real life scenario where I use 4 cores i7 6700 processor and the problem runs for hundreds of times with different sets.
I can overpay as much as I want, however - the value is correlate to the price. and so If I trade items worth 100 for 10 (prices) I lost 90 (you can think about dollars if it helps) and so just to break even the value I need to gain over +90.
I decide the values of each items from my own database