# 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.
• This is a knapsack problem, for which there exists no fast algorithm. Since you stated that you need an optimal solution, no approximation algorithms can be applied. The best known approach to get optimal solution is to apply dynamic programming technique of complexity $O(nW)$ where $W$ is not polynomial (probably ending up with $O(n2^n)$ – Simon Oct 5 '17 at 22:28
• I can use knapsack but it seems I can only do it on 1 inventory of items - can I somehow run knapsack dynamic programming on both my inventory and theirs?, how do I "cross" the results with my own items? – RythemOfTheDay Oct 5 '17 at 22:46
• So, to clarify, you're looking to get rid of items with a particular price and trade them for items with at most that price which you hope will have higher value? It seems a bit strange that you're willing to overpay but you assume your opponent/partner isn't. – David Richerby Oct 6 '17 at 11:18

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.

• I don't understand your approach. Can you spell it out more explicitly? I don't know what the "most significant item" is (how do you measure significance?), or what you mean by "a product sum that does not exceed the total or consumes all your inventory of that item". Do you claim that this gives the optimal solution? Do you have a proof of that? The original poster asked for an optimal solution, and it appears that an approximation is not good enough. I worry you're proposing a heuristic to compute an approximation; if so, that doesn't seem to answer the question that was asked. – D.W. Oct 6 '17 at 1:44
• Do you understand how SAR ADC's work by MSB then 2nd and so on by comparing with balance. Rank is P/V sort of items, I wonder if Q is relevant? – Tony Stewart Sunnyskyguy EE75 Oct 6 '17 at 2:03
• Analog in is the trade total value maximintegrated.com/en/app-notes/index.mvp/id/1080 – Tony Stewart Sunnyskyguy EE75 Oct 6 '17 at 2:10
• Not really sure how you I should use it, I kinda understand how SAR work so it will find range but how do I do it with a full set of items (and all their poissible prices). Would be great if you could elaborate more on that with maybe some example steps – RythemOfTheDay Oct 6 '17 at 20:35
• Did you want to assume Qty of 1 for each? or some integer from 0 to N? How do you want to define CUM cost per transaction? What if other person has different set of values V? – Tony Stewart Sunnyskyguy EE75 Oct 6 '17 at 21:59