Matching 2 sets of items by price 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:
My items:  


  Banana, P: 10, V: 5
  Pen, P: 3, V: 1
  Paper, P: 1, V: 1


Their Items:  


  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.
Assume you have a table of items of quantity Q, price P and Value, V and a computed value ratio P/V for each item.

I would use a Successive Approximation Register approach using the most significant item rated by P/V ratio using a product sum that does not exceed the total or consumes all your inventory of that item then repeat down your ranked list by Price/value ratio. Just as SAR is the fastest for ADC's, this would be my optimum solution.  

The trade may not be attractive to the other person, since you have offered items with the least value to you, so a practical solution must consider the V/P ratio of your item to  the other person, which may be unknown.

Tony
EE since 1975.