python - Recursive algorithm using memoization -

my problem follows: have list of missions each taking specific amount of time , grants specific amount of points, , time 'k' given perform them:

e.g: missions = [(14,3),(54,5),(5,4)] , time = 15

in example have 3 missions , first 1 gives me 14 points , takes 3 minutes. have 15 minutes total. each mission tuple first value being num of points mission , second value being num of minutes needed perform mission.

i have find recursively using memoization maximum amount of points able given list of missions , given time.

i trying implement function called choose(missions,time) operate recursively , use function choose_mem(missions,time,mem,k) achive goal. function choose_mem should 'k' number of missions choose from, , mem empty dictionary, mem, contain problems been solved before.

this got far, need implementing required above, mean dictionary usage (which there , empty time), , fact choose_mem function input i,j,missions,d , should choose_mem(missions, time, mem, k) mem = d , k number of missions choose from.

if can me adjust code appreciated.

mem = {}  def choose(missions, time):     j = time     result = []     in range(len(missions), 0, -1):         if choose_mem(missions, j, mem, i) != choose_mem(missions, j, mem, i-1):             j -= missions[i - 1][1]     return choose_mem(missions, time, mem, len(missions))   def choose_mem(missions, time, mem, k):      if k == 0: return 0     points, = missions[k - 1]     if > time:         return choose_mem(missions, time, mem, k-1)      else:         return max(choose_mem(missions, time, mem, k-1),                    choose_mem(missions, time-a, mem, k-1) + points) 

this bit vague, problem translated famous np-complete problem, knapsack problem.

you can read bit more on wikipedia, if replace weight time, have problem.

dynamic programming common way approach problem, can see here: http://en.wikipedia.org/wiki/knapsack_problem#dynamic_programming

memoization more or less equivalent dynamic programming, pratical matters, don't let fancy name fool you.

the base concept use additional data structure store parts of problem solved. since solution you're implementing recursive, many sub-problems overlap, , memoization allows calculate each of them once.

so, hard part think problem, what need store in dictionary, when call choose_mem values calculated, retrieve them dictionary, instead of doing recursive call.

if want check implementation of generic 0-1 knapsack problem (your case, since can't add items partially), seemed me resource:

https://sites.google.com/site/mikescoderama/home/0-1-knapsack-problem-in-p

it's explained, , code readable enough. if understand usage of matrix store costs, you'll have problem worked out you.