;renvoyer l' utilite d'un objet
(defun utilite (objet)
	(cadr objet)
)

;renvoyer le poid d'un objet
(defun poid (objet)
	(car objet)
)

;creer un sac (Utilité_totale (liste d'objets))
(defun creerSac ()
	(list 0 ())
)

;ajouter un objet a un sac en additionnant l'utilité de l'objet à l'utilité totale du sac
(defun ajoutObjetSac (sac objet)
	(cons (+ (car sac) (utilite objet)) (list (cons objet (cadr sac))))
)

;renvoyer le sac ayant la meilleure utilité totale
(defun meilleurSac (sac1 sac2)
	(if (> (car sac1) (car sac2))
		sac1
		sac2
	)
)

;fonction principale, renvoie le sac optimal
(defun sacOptimal (poidMax listeObjets)
	(cond
		;s'il n'y a plus d'objet à traiter le sac optimal est le sac vide
		((null listeObjets) (creerSac))
		
		;de meme si l'on cherche le sac optimal ayant une capacité maximum de 0
		((eq 0 poidMax) (creerSac))
		
		;si le poid du premier objet de la liste est supérieur au poid maximum du sac, autrement dit, 
		;si le sac ne peut pas contenir l'objet le sac optimal est donc le sac optimal avec le reste des objets 
		;et le meme poid maximum étant donné que l'on n'a pas ajouté le premier objet.
		((> (poid (car listeObjets)) poidMax) 
			(sacOptimal poidMax (cdr listeObjets))
		)
		
		;si le sac peut contenir le premier objet il faut choisir le meilleur sac résultant 
		;des actions : prendre l'objet ou ne pas le prendre
		(t (meilleurSac 
				;si on ne prend pas l'objet on calcul le sacOptimal avec le reste des objets
				(sacOptimal poidMax (cdr listeObjets)) 
				
				;si on prend l'objet on calcul le sac optimal avec le reste des objets pouvant le contenir, 
				;c'est à dire avec un poid diminué de (poid objet_courant) auquel on ajoute l'objet courant
				(ajoutObjetSac 	
					(sacOptimal (- poidMax (poid (car listeObjets))) 
								(cdr listeObjets)
					)
					(car listeObjets)
				)
			)
		)
	)
)

(defun JE1 (poid)
	(sacOptimal poid 
				'((1 6) (2 2) (3 3) (4 1) (5 5) (10 7) (4 3) (3 4) (2 5) (1 3))
	)
)

(defun JE2 (poid)
	(sacOptimal poid 
				'((1 6) (1 2) (1 3) (2 1) (2 5) (2 7) (2 3) (2 4) (2 5) (3 3)
				(3 5) (3 8) (4 4) (4 8) (4 5) (5 3) (5 6) (6 8) (7 5) (8 5))
	)
)

(defun JE3 (poid)
	(sacOptimal poid 
				'((1 8) (1 1) (1 9) (1 1) (1 5) (2 7) (2 4) (2 4) (2 2) (2 8)
				(3 9) (3 9) (3 5) (3 8) (3 3) (4 7) (4 4) (4 2) (4 5) (4 1)
				(5 5) (5 8) (5 4) (5 8) (5 5) (6 3) (6 6) (6 8) (6 5) (6 5)
				(7 5) (7 8) (7 4) (7 8) (7 5) (8 3) (8 6) (8 8) (8 5) (8 5)
				(9 5) (9 8) (9 4) (9 8) (9 5) (10 3) (10 6) (10 8) (10 5) (10 5))
	)
)

;; Acceder à un élément de coordonnées i j dans un tableau deux dimensions
(defun accesT2D (i j tab)
	(cond 
		((> i 0) (accesT2D (- i 1) j (cdr tab)))
		((> j 0) (accesT2D 0 (- j 1) (list (cdr (car tab)))))
		(t (car (car tab)))
	)
)

;; Création d'un tableau à deux dimensions de taille i j (fonction T2D)
(defun T2D (i j val)
	;; On appel la fonction colonne une unique fois de cette manière
	(tab i (colonne j val))
)

;; Associée à T2D : ajouter i colonnes pour créer le tableau
(defun tab (i C)
	(if (= 0 i)
		()
		(if (= 1 i)
			(list C)
			(cons C (tab (- i 1) C))
		)
	)
)

;; Associée à T2D : créer une colonne de taille size remplie avec la valeur val
(defun colonne (size val)
	(if (= 0 size)
		()
		(cons val (colonne (- size 1) val))
	)
)

;; Modifier une valeur dans le tableau à deux dimensions
(defun change (val i j tab)
	(cond 
		;on atteint la ieme colonne
		((> i 0) (cons (car tab) (change val (- i 1) j (cdr tab))))
		;puis la jieme ligne
		((> j 0) 	(cons 	(cons 	(car (car tab)) 
									(car 	(change 
													val 
													0 
													(- j 1) 
													(list (cdr (car tab)))
											)
									
									)
							) 
							(cdr tab)
					)
		)
		;on modifie la case
		(t 		 (cons (car (list (cons val (cdr (car tab))))) (cdr tab)))
	)
)

;On fourni à la fonction un tableau à deux dimensions T2D et l'objet courant, la fonction se charge de trouver le sac 
;optimal pour cette configuration en se basant sur les sac optimaux précédents.
(defun remplirCase (i j objet tab)
	(cond
		;si la case à modifier se trouve sur la premier ligne ou sur la premiere colonne on ne 
		;modifie rien car le sac optimal est le sac vide(tab est initialisé a (creerSac))
		((eq 0 i) tab)
		((eq 0 j) tab)
		
		;si le poid de l'objet est supérieur au poid maximum du sac, autrement dit, 
		;si le sac ne peut pas contenir l'objet le sac optimal est donc le sac optimal avec le reste des objets 
		;et le meme poid maximum étant donné que l'on n'a pas ajouté le premier objet.
		((> (poid objet) j) (change (accesT2D (- i 1) j tab) i j tab))
		
		;si le sac peut contenir le premier objet il faut choisir le meilleur sac résultant 
		;des actions : prendre l'objet ou ne pas le prendre
		(t (change 
								;si on ne prend pas l'objet on copie le sacOptimal 
								;avec le reste des objets
				(meilleurSac 	(accesT2D (- i 1) j tab)
								
								;si on prend l'objet on prend le sac optimal avec le reste des objets 
								;pouvant le contenir, c'est à dire avec un poid diminué de 
								;(poid objet_courant) auquel on ajoute l'objet courant
								(ajoutObjetSac 
									(accesT2D (- i 1) (- j (poid objet)) tab) 
									objet
								)
				)
				i 
				j 
				tab
			)
		)
	)
)

;Permet de créer une liste d'index pour parcourir un T2D colonnes par colonnes.
(defun creerIndex (debut_i fin_i debut_j fin_j)
	(cond
		((> debut_i fin_i) ())
		(t (append 	(creerColonne debut_i debut_j fin_j) 
					(creerIndex (1+ debut_i) fin_i debut_j fin_j)
			)
		)
	)
)

;Associée à créerIndex : permet de créer une colonne avec un certain index, allant de début à fin.
(defun creerColonne (index debut fin)
	(cond
		((> debut fin) ())
		(t (cons (list index debut) (creerColonne index (1+ debut) fin)))
	)
)

;Atteindre le ieme objet de liste
(defun iemeObjet (i listeObjets)
	(cond
		;le 0-ieme objet de la liste n'existe pas, on lui donne une valeure par défaut
		((eq 0 i) '(0 0))
		((eq 1 i) (car listeObjets))
		(t (iemeObjet (1- i) (cdr listeObjets)))
	)
)

;Deuxieme version pour résoudre le problème
(defun sacOptimalb (poidMax objets)
	;On crée une variable contenant un tableau initialisé à creerSac (sac vide)
	(set 'X (T2D (1+ (length objets)) (1+ poidMax) (creerSac)))
	
	;On crée une variable contenant la liste des objets pour pouvoir la parcourir dans la fonction suivante
	(set 'O objets)
	
	;On utilise mapcar sur la liste d'index pour appliquer à chaque case du tableau la fonction f
	(mapcar 'f (creerIndex 1 (length objets) 1 poidMax))
	
	;On retourne la solution finale
	(accesT2D (length objets) poidMax X)
) 

;Index contient une liste d'index : pour chaque couple d'index on met à jour X 
(defun f (index)
	(set 'X (remplirCase 	(car index) 
							(cadr index) 
							(iemeObjet (car index) O) 
							X
			)
	)
)

(defun JE1b (poid)
	(sacOptimalb poid 
				'((1 6) (2 2) (3 3) (4 1) (5 5) (10 7) (4 3) (3 4) (2 5) (1 3))
	)
)

(defun JE2b (poid)
	(sacOptimalb poid 
				'((1 6) (1 2) (1 3) (2 1) (2 5) (2 7) (2 3) (2 4) (2 5) (3 3)
				(3 5) (3 8) (4 4) (4 8) (4 5) (5 3) (5 6) (6 8) (7 5) (8 5))
	)
)

(defun JE3b (poid)
	(sacOptimalb poid 
				'((1 8) (1 1) (1 9) (1 1) (1 5) (2 7) (2 4) (2 4) (2 2) (2 8)
				(3 9) (3 9) (3 5) (3 8) (3 3) (4 7) (4 4) (4 2) (4 5) (4 1)
				(5 5) (5 8) (5 4) (5 8) (5 5) (6 3) (6 6) (6 8) (6 5) (6 5)
				(7 5) (7 8) (7 4) (7 8) (7 5) (8 3) (8 6) (8 8) (8 5) (8 5)
				(9 5) (9 8) (9 4) (9 8) (9 5) (10 3) (10 6) (10 8) (10 5) (10 5))
	)
)

(defun JE4b (poid)
	(sacOptimalb poid 
				'((1 2) (1 3) (1 9) (1 11) (1 13) (1 15) (1 17) (1 18) (11 10) (11 13)
				(2 3) (2 3) (2 5) (2 8) (2 12) (2 14) (2 17) (2 19) (12 2) (12 4)
				(3 2) (3 4) (3 5) (3 8) (3 9) (3 9) (3 9) (3 12) (13 7) (13 11)
				(4 1) (4 4) (4 4) (4 5) (4 5) (4 11) (4 14) (4 15) (14 8) (14 16)
				(5 2) (5 3) (5 4) (5 8) (5 14) (5 15) (5 15) (5 18) (15 4) (15 13)
				(6 3) (6 6) (6 8) (6 8) (6 10) (6 13) (6 15) (6 17) (16 6) (16 9)
				(7 5) (7 5) (7 7) (7 8) (7 11) (7 14) (7 17) (7 17) (17 2) (17 9)
				(8 3) (8 6) (8 8) (8 9) (8 10) (8 11) (8 11) (8 15) (18 9) (18 10)
				(9 1) (9 3) (9 6) (9 7) (9 7) (9 16) (9 16) (9 17) (19 4) (19 19)
				(10 3) (10 6) (10 8) (10 9) (10 12) (10 15) (10 16) (10 16) (20 6) (20 8))
	)
)


(defun timeClisp (fnc)
	(let ((v1 (get-internal-real-time)))
		(print (eval fnc))
		(let ((v2 (get-internal-real-time)))
			(/ (float (- v2 v1)) (float internal-time-units-per-second))
		)
	)
)

(defun timeEmacs (fnc)
	(let ((v1 (float-time)))
		(print (eval fnc))
		(let ((v2 (float-time)))
			(- v2 v1)
		)
	)
)