Matching 2 sets of items by price

Question

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

Answer 1

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.

Answer 2

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