# 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? Oct 5, 2017 at 19:40
• Consider buying a quantum computer, they are well suited for this type of problem ;) Jan 4, 2018 at 15:17

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 Oct 5, 2017 at 19:49
• You can throw those out, since you'll never want them. 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. 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. 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. 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);
}

//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;
//you at least need to gain 90 in value
if (delta_value >= delta_overpaid) {