按价格匹配2套商品

Question

我试图用我能找到的最有效的方法来解决以下问题。

我想把我的物品换成别人的物品，每件东西都有价格和价值。

我希望最大限度地提高我所交易的物品的价值，例如：

My项目：

Banana, P: 10, V: 5  
Pen, P:3, V:1  
Paper, P: 1, V: 1  

他们的项目：

Phone, P: 10, V: 8  
Key, P: 1, V: 2  
Wallet, P: 30, V: 100  

你可以看到，我可以用手机和钥匙(价值10)交换我的香蕉和纸(价值6)。

我可以多付，但不能少付，我多付的钱也损失了。目前，我的解决方案是使用生成所有可能的组合我的项目，并试图匹配价格与背包算法，并检查每个结果。

然而，这是非常不有效的，因为我可以有1000多个项目(包括我的和其他人)。

有人能找到解决这个问题的办法吗？我需要它是有效的，但也给我最好的解决方案(最佳价值)。

• 这些项目并不是无限的，它们是有限度的。
• 我真的没有一个规模，它需要有多高的效率，我需要它在现实生活场景中，我使用了4个核心i7 6700处理器，并且这个问题在不同的集合中运行了数百次。
• 不过，我可以多付多少钱因此，如果我把价值100的东西换成10 (价格)，我损失了90美元(如果有帮助的话，你可以考虑美元)，所以为了达到平衡，我需要获得超过+90的价值。
• 我从我自己的数据库中决定每个项目的值。

Answer 1

作为起点..。

将它们的项目按价值除以成本，按降序排序。这给你一个清单，他们的项目与最有价值的项目在顶部。从列表的顶部选择项目，直到所选项目的成本之和满足固定成本为止。避免选择没有值的项(v=0)。

然后，按价值除以成本，按升序排序您的项目。这给出了你的物品清单，上面列出了最不值钱的物品。从列表的顶部选择项目，直到所选项目的成本之和满足相同的固定成本为止。

如果其项目的总价值/成本比超过了项目的总价值/成本比率(在对两个选定列表之间的价格差异进行调整后)，则可以将所选项目交换为所选项目。

Answer 2

根据你们的意见，我建议采取以下办法：

//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);
        } 
    }
}

这方面的时间将是O(n log n)用于分类，理想情况下O(n log n)用于查找最佳交易(我的列表中的每一项，并对其列表中的项目进行二进制搜索)。