Find highest total price by selling items to multiple buyers, limited by user input to how many separate sales can be made

EDIT: Im sorry guys my explantion of the problem wasn't clear! This should be better:

1. User sends ID numbers of articles and the max. number of bundles(packages)

2. API searches for all prices available for the articles and calculates best result for min. numbe开发者_开发问答r of bundles (limit to max. number provided by customer) ONE Bundle is one package of items delivered to ONE platform(buyer)

Thanks!

This is a fun little problem. I spent a few hours on it this morning, and while I don't have a complete solution, I think I have enough for you to get started (which I believe was what you asked for).

First of all, I'm assuming these things, based on your description of the problem:

• All buyers quote a price for all the items
• There's no assumption about the items, they may all be different
• The user can only interact with a limited number of buyers
• The user wants to sell every item, each to one buyer
• The user may sell multiple items to a single buyer

Exact solution -- brute force approach

For this, the first thing to realize is that, for a given set of buyers, it is straight forward to calculate the maximum total revenue, because you can just choose the highest price offered in that set of buyers for each item. Add up all those highest prices, and you have the max total revenue for that set of buyers.

Now all you have to do is make that calculation for every possible combination of buyers. That's a basic combinations problem: "n choose k" where n is the total number of buyers and k is the number of buyers you're limited to. There are functions out there that will generate lists of these combinations (I wrote my own... there's also this PEAR package for php).

Once you have a max total revenue for every combination of chosen buyers, just pick the biggest one, and you've solved the problem.

More elegant algorithm?

However, as I intimated by calling this "brute force", the above is not fast, and scales horribly. My machine runs out of memory with 20 buyers and 20 items. I'm sure a better algorithm exists, and I've got a good one, but it isn't perfect.

It's based on opportunity costs. I calculate the difference between the highest price and the second highest price for each item. That difference is an opportunity cost for not picking the buyer with that highest price.

Then I pick buyers offering high prices for items where the opportunity cost is the highest (thus avoiding the worst opportunity costs), until I have k - 1 buyers (where k is the max I can pick). The final choice is tricky, and instead of writing a much more complicated algorithm, I just run all the possibilities for the final buyer and pick the best revenue.

This strategy picks the best combination most of the time, and if it misses, it doesn't miss much. Its also scales relatively well. It's 10x faster than brute force on small scales, and if I quadruple all the parameters (buyers, buyer limit, and items), calculation time goes up by a factor of 20. Considering how many combinations are involved, that's pretty good.

I've got some code drafted, but it's too long for this post. Let me know if you're interested, and I'll figure out a way to send it to you.

This is a graph problem. It can be solved with the Edmond's Blossom V algorithm. It's a matching algorithm to find the best pairwise matching for example in dating programs. Maybe you want to look for the 1d bin-packing algorithm. In 1d bin-packing you have a limit items to assign to unlimited boxes or shelves the better the boxes get filled.

If I understand the problem correctly, it is NP-complete via reduction from Minimum Set Cover. We can translate an instance of Set Cover into an instance of the OP's problem as follows:

Let an instance of Set Cover be given by a set X of size n and a collection of subsets S_1, S_2, ..., S_m of X. Construct an instance of the OP's problem where the seller has n items to sell to m buyers, where buyer i offers a price of 1 for item j if *S_i* contains item j and 0 otherwise. A solution to the OP's problem where the number of buyers is limited by k and the total price paid is n corresponds to a solution to the original Set Cover problem with k sets. So, if you had a polynomial-time solution to the OP's problem, you could solve Minimum Set Cover by successively solving it for the case of 1, 2, 3, etc... buyers until you found a solution with total price equal to n.