0
$\begingroup$

To dumb it down to basics, lets say I have a struct called item that looks like this:

struct item {
    int power, cost;
};

then I have 2 arrays of these items, each filled with N items with various amounts of power/cost

Then I want a list of combinations of these items (item a + item b) where each item must have the highest(or equal to highest) amount of power among other possibilities with the same cost.

One way to get this list is as follow (in pseudo code)

item arrays are A and B

declare array C
do a nested loop through all the combinations of A and B and add these combinations to C
now C contains all the possible combinations

sort C by in an ascending order by cost

declare array D
loop through all the items in C and if
-the item power is higher or equal than the current highest power
-the cost is equal or lower
then if 
-the cost is higher than the current highest
   add element to D
else -the cost is equal or lower
   replace last element of D with this one

It works but the amount of memory required for the algorithm is a.size * b.size + then some which is way too much for the 24kB i have available.

A and B aren't random though, due to the nature of the data, the amount of viable combinations is actually less than either A or B.

I'm looking for an algorithm to get the same result as described above but with much less memory use.

I tried one idea I had -

sort A and B by cost in ascending order

while i havent looked to the end of both arrays do
    find next A that in combination with last B has greater or equal power than current highest and mark it down
    find next B that in combination with last A has greater or equal power than current highest and mark it down

    add 1 - 3 elements to D depending on a chain of conditions described in the last snippet, possibly A product, B product and the product of both A and B index

It sorta works but not perfectly, it misses some good combinations and due to that adds some bad combinations. I'm trying to fix it but meanwhile.. figured I'd ask here.

EDIT: to further clarify what I mean, I'll solve a small example with the working (but memory hungry) method

lets say the input is as follows:

A[0].power = 3; A[0].cost = 1;
A[1].power = 5; A[1].cost = 3;
A[2].power = 7; A[2].cost = 8;

B[0].power = 2; B[0].cost = 2
B[1].power = 4; B[1].cost = 3
B[2].power = 1; B[2].cost = 4

As you can see, both arrays are already ordered by cost so we can skip doing that, we can however eliminate B[2] because it has a lower power and higher cost than other options in B and will only yield combinations that would be removed anyway.

Next we combine all of them

(first number between curly brackets indicates power, second cost)
A[0] + B[0] = {5, 3); A[0] + B[1] = {7, 4}
A[1] + B[0] = {7, 5); A[1] + B[1] = {9, 6}
A[2] + B[0] = {9, 10); A[2] + B[1] = {8, 12}

then we list combinations by cost (note that in this example they just happened to be in the right order already, this is not always the case)

{5, 3}, {7, 4}, {7, 5}, {9, 6}, {9, 10}, {8, 12}

Now we can eliminate {7, 5}, {9, 10} and {8, 12} because they yield no improvement of power over equivalent or lower cost options

final result

{5, 3}, {7, 4}, {9, 6}

I'm looking for a way to calculate either all of the final results or better yet, calculate the results on demand by index (they would still be requested in a sequential manner so possibly an algorithm that calculates all of them is the right sequence could be modified to do that). That is because while all the results will very likely fit in the memory, I realized that the theoretical maximum is still A.size * B.size and I cant have it crash under an exceptional circumstance.

$\endgroup$
  • 1
    $\begingroup$ I can't understand your problem description. In particular, I can't tell what the input and desired output is. It appears that the input is two arrays $A[]$ and $B[]$, each containing $N$ items. What is the desired output? What do you mean by "a combination where each item...."? Can you define the condition more precisely and a bit more slowly, perhaps using suitable mathematical notations? $\endgroup$ – D.W. Mar 23 '15 at 6:20
  • $\begingroup$ Also, what is the question? $\endgroup$ – Raphael Mar 23 '15 at 6:23
  • $\begingroup$ @Raphael "I'm looking for an algorithm to get the same result as described above but with much less memory use" implies a question. $\endgroup$ – David Richerby Mar 23 '15 at 7:51
  • 1
    $\begingroup$ Does the power/cost of a combination equal the sum of the powers/costs of the items involved in the combination? $\endgroup$ – Tom van der Zanden Mar 23 '15 at 9:25
  • $\begingroup$ @TomvanderZanden yes $\endgroup$ – user29075 Mar 23 '15 at 19:16