There are P products {p0, p1, p2, p3,... p(P-1)}.

There are N planets {n0, n1, n2, n3, ... n(N-1)}.

The cost of each product, and if it can be traded on that planet, C(n, p) is different on each planet. (If C(n, p)==0 then p cannot be bought or sold)

The cost of each product is deterministic (C(n, p) never changes for a given combination of n and p), but there is no pattern to availability or cost.

A product sells for 10% less than the purchase price.

The algorithm musst be deterministic. (No probabilistic methods.)

My solution:

- Code: Select all
`for (i=0; i<P; i++) { //Source Planet`

for (j=0; j<P; j++) { //Destination Planet

maxValue = 0;

maxProduct = -1;

for (k=0; k<N; k++) { //Product to carry

if ((C(i, k)>0) && (C(j, k) > C(i, k)) { //Ensure both planets deal in product

tradeValue = (.9 * C(j, k)) - C(i, k);

if (tradeValue > maxValue) {

maxValue = tradeValue;

maxProduct = k;

}

}

}//Next k

/* Do something with per-path result */

}//Next j

}//Next i

This function yields correct results (assuming no typos), but has a runtime of O(PN^2). Can better be done?