Paste Search Dynamic
def resolve
  1. #Imports
  2. import sys
  3.  
  4. class Rep():
  5.     def __init__(self):
  6.         sys.setrecursionlimit(10000000)
  7.         self.res = none
  8.         self.rep()
  9.  
  10.     def resolve(self, filename):
  11.         with open(filename, "r") as file:
  12.             content = file.readlines()
  13.  
  14.         (vTot, nbrObjets) = (int(x) for x in content[0].split())
  15.         objets            = [int(x) for x in content[1].split()]
  16.  
  17.         objetsSort        = objets.copy()
  18.         objetsSort.sort(reverse=true)
  19.         self.save  = objetsSort.copy()
  20.  
  21.         self.resolveBranchWithoutRecursion(vTot, objetsSort)
  22.  
  23.     def resolveBranch(self, maxi, liste, res=[], actual=0):
  24.         if actual == maxi:
  25.             self.res = res
  26.             return true
  27.  
  28.         if len(liste) != 0:
  29.             if actual + liste[0] <= maxi:
  30.                 rep       = liste.pop(0)
  31.                 res.append(rep)
  32.                 actual += rep
  33.             else:
  34.                 liste.pop(0)
  35.         else:
  36.             if res[-1] != self.save[-1]:
  37.                 liste   = self.save[self.save.index(res[-1])+1:]
  38.                 actual -= res.pop()
  39.             else:
  40.                 print("### DEBUG ###")
  41.                 print("Liste :", liste)
  42.                 print("Res :", res)
  43.                 print("Actual :", actual)
  44.                 print("Maxi :", maxi)
  45.                 print("#############\n")
  46.                 liste  = self.save[self.save.index(res[0])+1:]
  47.                 actual = 0
  48.                 res    = []
  49.        
  50.         return self.resolveBranch(maxi, liste, res, actual)
  51.  
  52.     def resolveBranchWithoutRecursion(self, maxi, liste):
  53.         actual = 0
  54.         res    = []
  55.         index  = -1
  56.  
  57.         while actual != maxi:
  58.             if len(liste) != 0:
  59.                 if actual + liste[0] <= maxi:
  60.                     rep       = liste.pop(0)
  61.                     res.append(rep)
  62.                     actual += rep
  63.                 else:
  64.                     liste.pop(0)
  65.             else:
  66.                 if res[-1] != self.save[-1]:
  67.                     liste   = self.save[self.save.index(res[index])+1:]
  68.                     actual -= res.pop()
  69.                 else:
  70.                     liste  = self.save[self.save.index(res[index])+1:]
  71.                     actual = 0
  72.                     res    = []
  73.        
  74.             print("### DEBUG ###")
  75.             print("Liste :", liste)
  76.             print("Res :", res)
  77.             print("Actual :", actual)
  78.             print("Maxi :", maxi)
  79.             print("#############\n")
  80.  
  81.         return res
  82.  
  83.     def rep(self):
  84.         end = []
  85.         print(self.resolve("fichier_a_petit.in"))
  86.        
  87.  
  88. if __name__ == "__main__":
  89.     Rep()
Parsed in 0.022 seconds