python - Optimizing this dynamic programming solution -

problem:

you given array m of size n, each value of m composed of weight w, , percentage p.

m = [m0, m1, m2, ... , mn] = [[m0w, m0p], [m1w, m1p], [m2w, m2p], ..., [mnw, mnp] ]

so we'll represent in python list of lists.

we trying find minimum value of function:

def minimize_me(m):     t = 0     w = 1     in range(len(m)):         current = m[i]         t += w * current[0]         w *= current[1]     return t 

where thing can change m ordering. (i. e. rearrange elements of m in way) additionally, needs complete in better o(n!).

brute force solution:

import itertools import sys  min_t = sys.maxint min_permutation = none  permutation in itertools.permutations(m):     t = minimize_me(list(permutation), 0, 1)     if t < min_t:         min_t = t         min_permutation = list(permutation) 

ideas on how optimize:

the idea:

instead of finding best order, see if can find way compare 2 given values in m, when know state of problem. (the code might explain more clearly). if can build using bottom-up approach (so, starting end, assuming have no optimal solution) , can create equation can compare 2 values in m , 1 definitively better other, can construct optimal solution, using new value, , comparing next set of values of m.

the code:

import itertools  def compare_m(a, b, v):     a_first = b[0] + b[1] * (a[0] + a[1] * v)     b_first = a[0] + a[1] * (b[0] + b[1] * v)      if a_first > b_first:         return a, a_first     else:         return b, b_first  best_ordering = [] v = 0  while len(m) > 1:     best_pair_t = sys.maxint     best_m = none      pair in itertools.combinations(m, 2):         m, pair_t = compare_m(pair[0], pair[1], v)         if pair_t < best_pair_t:             best_pair_t = pair_t             best_m = m      best_ordering.append(best_m)     m.remove(best_m)     v = best_m[0] + best_m[1] * v  first = m[0] best_ordering.append(first) 

however, not working intended. first value right, , 60-75% of time, entire solution optimal. however, in cases, looks way changing value v gets passed compare evaluating higher should. here's script i'm using test against:

import random  m = [] in range(0, 5):     w = random.randint(1, 1023)     p = random.uniform(0.01, 0.99)     m.append([w, p]) 

here's particular test case demonstrating error:

m = [[493, 0.7181996086105675], [971, 0.19915848527349228], [736, 0.5184210526315789], [591, 0.5904761904761905], [467, 0.6161290322580645]] 

optimal solution (just indices) = [1, 4, 3, 2, 0] solution (just indices) = [4, 3, 1, 2, 0]

it feels close, cannot life of me figure out wrong. looking @ wrong way? seem it's on right track? or feedback appreciated!

we don't need information current state of algorithm decide elements of m better. can sort values using following key:

def key(x):     w, p = x     return w/(1-p)  m.sort(key=key) 

this requires explanation.

suppose (w1, p1) directly before (w2, p2) in array. after processing these 2 items, t increased increment of w * (w1 + p1*w2) , w multiplied factor of p1*p2. if switch order of these items, t increased increment of w * (w2 + p2*w1) , w multiplied factor of p1*p2. clearly, should perform switch if (w1 + p1*w2) > (w2 + p2*w1), or equivalently after little algebra, if w1/(1-p1) > w2/(1-p2). if w1/(1-p1) <= w2/(1-p2), can these 2 elements of m "correctly" ordered.

in optimal ordering of m, there no pair of adjacent items worth switching; adjacent pair of (w1, p1) , (w2, p2), have w1/(1-p1) <= w2/(1-p2). since relation of having w1/(1-p1) <= w2/(1-p2) natural total ordering on w/(1-p) values, fact w1/(1-p1) <= w2/(1-p2) holds pair of adjacent items means list sorted w/(1-p) values.

---

your attempted solution fails because considers pair of elements value of tail of array. doesn't consider fact rather using low-p element now, minimize value of tail, might better save later, can apply multiplier more elements of m.

---

note proof of our algorithm's validity relies on p values being @ least 0 , strictly less 1. if p 1, can't divide 1-p, , if p greater 1, dividing 1-p reverses direction of inequality. these problems can resolved using comparator or more sophisticated sort key. if p less 0, w can switch sign, reverses logic of items should switched. do need know current state of algorithm decide elements better, , i'm not sure then.