1    def solveCell(dpt,row,col,instance):
   2      """ Solves recursively the cell at given coordinates. """
   3      if (dpt[row][col]!=-1): return 0
   4      if (col==0): return 0
   5      weight_i = instance.items[col-1].weight;
   6      v1=solveCell(dpt,row,col-1,instance)
   7      if (row-weight_i<0):
   8        dpt[row][col]=dpt[row][col-1]
   9        return v1+1;
  10      else:
  11        v2=solveCell(dpt,row-weight_i,col-1,instance)
  12        dpt[row][col]=max(dpt[row][col-1],dpt[row-weight_i][col-1]+instance.items[col-1].price)
  13        return v1+v2+1
  14    
  15    def method_dynamicProgFast(instance,state):
  16      """ Solves the instace using the recursive dynamic programming. Returns tuple (best result, empty list, computed cells. ""
        "
  17      dpt=[]
  18      for i in range(instance.maxWeight+1):
  19        dpl=[]
  20        dpl.append(0)
  21        for j in range(1,instance.size()+1):
  22          dpl.append(-1)
  23        dpt.append(dpl)
  24      states=solveCell(dpt,instance.maxWeight,instance.size(),instance)
  25      return (dpt[instance.maxWeight][instance.size()],[],states)