################################################################################
################################################################################
#   PROBLEME DU SAC-A-DOS
################################################################################
################################################################################


import numpy as np
from collections import deque


################################################################################
#   SCENARIO DE TEST
################################################################################

C=15
X=((1,2),(2,5),(3,7),(7,12),(10,9),(11,15),(1,1),(2,1))

################################################################################
#   
################################################################################


def KP_rec(X,C):
    # A COMPLETER
    pass

print("Approche descendante sans mémoïsation")
print(KP_rec(X,C))
print()

################################################################################
#   
################################################################################


def KP_memo(X,C):
    # A COMPLETER
    pass

print("Approche descendante avec mémoïsation")
print(KP_memo(X,C))
print()


################################################################################
#   
################################################################################

def KP_tab(X,C):
    # A COMPLETER
    pass

print("Matrice de l'approche ascendante")
print(np.array(KP_tab(X,C)))
print()

def KP_comp(X,C):
    tab=KP_tab(X,C)
    # A COMPLETER
    pass

print("Approche ascendante - une composition")
print(KP_comp(X,C))
print()

################################################################################
#   
################################################################################


def KP_all(X,C):
    n=len(X)
    tab=KP_tab(X,C)
    file_KP=deque()
    res=[]
    file_KP.append([(n,C),[]])
    # A COMPLETER
    pass

print("Approche ascendante - toutes les compositions")
print(KP_all(X,C))
print()