2

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

| improve this answer | |
  • Consider this list of their items: Pocket Lint, P: 14, V: 0 – candied_orange Oct 5 '17 at 19:49
  • You can throw those out, since you'll never want them. – Robert Harvey Oct 5 '17 at 19:51
  • 1
    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. – candied_orange Oct 5 '17 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. – Robert Harvey Oct 5 '17 at 19:53
  • 1
    Worth noting: If their items suddenly become less valuable than yours (in sorted order), then you can stop iterating. – Robert Harvey Oct 6 '17 at 1:08
0

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

| improve this answer | |
  • Doesn't seems like it would work at all, here the nodejs code I wrote: jsfiddle.net/5cL00zd5 Did I miss anything? – RythemOfTheDay Oct 6 '17 at 15:50
  • I'll take a look in your code. But did you get the logic? – Emerson Cardoso Oct 6 '17 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. – Emerson Cardoso Oct 6 '17 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 – Emerson Cardoso Oct 6 '17 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 – RythemOfTheDay Oct 6 '17 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.