I have two arrays of objects (items) in the exact same format. Each item represents a wager, and each array represents one of two outcomes for that wager (ex: Team A vs Team B). Both arrays look like this to start with:
{
"_id": "55762b3de624f37d80d09b34",
"value": 803,
"owner": 923
},
{
"_id": "55762b3dc73fad717a7173ed",
"value": 1457,
"owner": 897
},
...
These arrays differ in length. Let's say array A has 1200 items and array B has 800 items with each item's value ranging from 4 to 5,000. In production each array will likely range from 1000-200,000 entries, so keep efficiency in mind. The goal is to take all the items in array B (lost wagers) and add them to array A (won wagers) so that the value of items in B are distributed evenly by sum of values grouped by user in A. So if you bet three items, you would get those items back plus any number of items from array B.
First I run through array A (winners) and handle the user grouping and summing. Array A is now Object A and looks like this:
'997': // User ID
{ bet: 15090, // Summed value of all items wagered in the below array
items: // Original item IDs from their wager
[ '55762b3dd82338e9683eea9b',
'55762b3dccd4800148eec868',
'55762b3de495cbcd594ecc17',
'55762b3daad995d207c506f0',
'55762b3d2154c4c0e273fe94' ] },
'998':
{ bet: 5196,
items: [ '55762b3da1e658e5cb37ede6', '55762b3d1fca60c0cdd21a2e' ] },
...
Then take the total value of each array and figure out the multiplier to use for each "bet" value (aka: calculate the odds). Using the same randomly generated data this works out to be:
A Total Value: 2,439,112 (entire value of items bet on Team A)
B Total Value: 1,608,947 (entire value of items lost on Team B)
0.6596445755668456 value from B for each A
So, for instance, user 997
's total bet of 15,090 would need to gain ~9,954 of value from array B. When the items from array B are used, they are removed and the _id field is added to the "items" array. Since the values are associated with individual items and not a divisible currency, they cannot be split in order to make perfect change. The values don't have to match up exactly, but should be relatively close. For example, if a user bets 100 and should gain 65.9, they can get items within the 62-68 range if needed. This also means that users who bet very little may end up getting nothing in return depending on the odds, since there is a minimum bet of 4. Ex: If you bet 4, your winnings would be 2.63, but the lowest item value to distribute is 4.
What type of algorithm would be most appropriate for this kind of task? It sounds like something straight out of a textbook, but I have no idea where to start my search.
All this data will eventually be in mongodb, so mongo-specific functions are welcomed as well!