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

• 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

• Please define this trade better in the question (not in these comments). In this trade how much are you overpaying? Is value considered at all by these other people or is value only about what you think? Commented Oct 5, 2017 at 19:40
• Consider buying a quantum computer, they are well suited for this type of problem ;) Commented Jan 4, 2018 at 15:17

## 2 Answers

As a starting point...

Sort their items by value divided by cost, in descending order. This gives you a list of their items with the most valuable items at the top. Select items from the top of this list until the sum of the cost of the selected items meets a fixed cost. Avoid selecting items having no value (v=0).

Then sort your items by value divided by cost, in ascending order. This gives you a list of your items with the least valuable items at the top. Select items from the top of this list until the sum of the cost of the selected items meets the same fixed cost.

If the overall value/cost ratio of their items exceeds the overall value/cost ratio of your items (after adjusting for any difference in price between the two selected lists), you can trade your selected items for their selected items.

• Consider this list of their items: Pocket Lint, P: 14, V: 0 Commented Oct 5, 2017 at 19:49
• You can throw those out, since you'll never want them. Commented Oct 5, 2017 at 19:51
• My point is you need to stop and consider the value you're exchanging. Not just match price to price. Sometimes you're better off with what you already have. Commented Oct 5, 2017 at 19:53
• The answer in it's current form considers value divided by cost. Think: signal to noise ratio. Naturally, you'll have to consider the final value/cost ratios of each selected list before you make the trade. Commented Oct 5, 2017 at 19:53
• Worth noting: If their items suddenly become less valuable than yours (in sorted order), then you can stop iterating. Commented Oct 6, 2017 at 1:08

Based on you comments, I suggest the following approach:

``````//Define your data structure
typedef struct {
int price;
int value;
} Item;

//Sorts by price, then by value in Ascending order (for my items)
bool asc_price_val(Item a, Item b) {
if (a.price == b.price)
return a.value < b.value;
else
return a.price < b.price;
}

//Descending order of the previous (for their items)
bool desc_price_val(Item a, Item b) {
return !comp_ascending(a,b);
}

void find_best_trades(std::vector<Item>& my_items, std::vector<Item>& their_items){

//sort my items by value and price, least-valued first
std::sort(my_items.begin(), my_items.end(), asc_price_val);

//sort their items by value and price in descending order
std::sort(their_items.begin(), their_items.end(), desc_price_val);

//Iterate over my items
for (auto my_it = my_items.begin(); my_it != my_items.end(); ++my_it) {

//Use binary search here on their items, in order to quickly search
//an item with the same price. If you don't find the same price,
//then keep trying to find a smaller price
auto theirs = find_best_valued_item_by_price(my_it->price, their_items);

auto delta_value = theirs->value - my_it->value;
auto delta_overpaid = my_it->price - theirs->price;

//Check if this trade worths the overpaid;
//According to your comments, if you lose 90 in price,
//you at least need to gain 90 in value
if (delta_value >= delta_overpaid) {
trade(my_it, their);
}
}
}
``````

Time for this will be O(n log n) for the sortings, and ideally O(n log n) for finding the best trades (each item in my list, with a binary search for an item in their list).

• Doesn't seems like it would work at all, here the nodejs code I wrote: jsfiddle.net/5cL00zd5 Did I miss anything? Commented Oct 6, 2017 at 15:50
• I'll take a look in your code. But did you get the logic? Commented Oct 6, 2017 at 17:00
• Hey, the sort for TheirItems is wrong; I suggested to be in descending order but this actually crashes the binary search; it can be sorted using the ascending order; it seems it solved the problem. Commented Oct 6, 2017 at 17:14
• There were a few typos in the code; I fixed them for you. Also, the sorting was incorrect to, I changed it to be ascending for the 'bs' to work; jsfiddle.net/0fnouwk0 Commented Oct 6, 2017 at 17:27
• I think I understand the code but I think it still won't find me the best matches. For example: jsfiddle.net/gwr0vn40 if I change my items properties it will return { itemName: 'Paper', delta: 1, price: 1 } { itemName: 'Key', delta: 2, price: 1 } delta_value: 1 delta_overpaid: 0 TRADE! delta_value: 1 although I can trade my banana and paper for a phone and get 2 delta (8-6) so it is not the best value I can get Commented Oct 6, 2017 at 20:12