# ###################################################################
#
#       Program: sad_heuristique.py
#        Author: Jean-Michel Richer
#  Organisation: Computer Science Department, 
#                University of Angers,
#	             France
#         Email: jean-michel.richer@univ-angers.fr
# Creation date: April, 2021
#  Modification: April, 2021
#
# ###################################################################
# 
# Aim:
#
#    This program is an implementation of a heuristic method used
#    to find a solution to the knapsack problem. The method is
#    derived from https://interstices.info/le-probleme-du-sac-a-dos/
#    and uses the ratio profit / weight of each object
#
# Objectif :
#
#    Ce programme repose sur l'utilisation d'une heuristique afin
#    de résoudre le problème du sac à dos. La méthode est issue
#    du site https://interstices.info/le-probleme-du-sac-a-dos/
#    et repose sur l'utilisation du ratio profit / poids des objets
#
# ###################################################################
#
# License
#
#    This program is a free software you can modifiy it and 
#    redistribute it for non profitable use. 
#
# ###################################################################


import random
import sys

#
# Données du problème
# Poids maximum autorisé et données de poids et profit
# 

poids_maximum = 269
poids   = [ 95, 4, 60, 32, 23, 72, 80, 62, 65, 46]
profits = [ 55, 10, 47, 5, 4, 50, 8, 61, 85, 87 ]

# ===================================================================
# Classe qui permet de représenter les objets à mettre dans le sac
# à dos. Un objet possède un poids, un profit et un ratio égal au
# rapport profit / poids
# ===================================================================
class Objet(object):

	"""
	class used to represent an object
		
	Attributes
	----------
	poids : int
	  weight of the object
	profit : int
	  profit of the object
	ratio : float
	  ratio profit / poids
	  
	Methods
	-------
	 __str__()
	   transform the object into a string 
	"""
	
	def __init__(self, id, poids, profit):
		"""
    	Constructor
    	
    	Parameters
    	----------
    	id : int
    	  object identifier from 1 to N
    	poids : int 
    	  weight of the object
    	profit : int
    	  profit de l'objet 
    		
		"""
		self.id = id
		self.profit = profit
		self.poids = poids
		self.ratio = profit / poids
    
	def __str__(self):
		"""
    	Transform the object into a string    
		"""    
		return "(" + str(self.id) + ",p=" + str(self.poids) + ",w=" + str(self.profit) + ",r={0:.2f}".format(self.ratio) + ")"
        

# ===================================================================
# Classe qui permet de représenter un sac à dos composé d'une liste
# de présence/absence d'objets, du poids et profit total qui 
# résulte de la présence/absence des objets
# ===================================================================
class Sac(object):
	"""
	Knapsack representation as a list of present/absent objects,
	the weight and the profit
	
	Attributes
	----------
	objets : list
		list of objects that can be put inside the knapsack
	liste : list
		list of 0 and 1, 1 means the object is present
	poids : int
		weight of the knapsack
	profit : int 
		profit of the knapsack
	
	
	"""
	
	# -----------------------------------------------------
	# Constructeur avec liste d'objets et liste 
	# présence / absence des objets
	# -----------------------------------------------------
	def __init__(self, objets, liste):
		"""
		Constructor
		
		Parameters
		----------
		objets : list of Objet
		  list of all possible objects that can be put 
		  in the knapsack
		liste : list of 0/1 
		  list of objects that compose the knapsack
		  
		"""
		self.objets = objets
		self.liste = liste
		self.poids = 0
		self.profit = 0
		
		for i in range(len(liste)):
			if liste[ i ] == 1:
				self.poids += objets[ i ].poids
				self.profit += objets[ i ].profit
	
		self.verbose = True
		
	# -----------------------------------------------------
	# ajouter un objet dans le sac à dos
	# -----------------------------------------------------
	def ajoute_objet(self, n):
		"""
		Add object to knapsack
		"""
		if self.liste[ n ] == 1:
			return
		self.poids += self.objets[ n ].poids
		self.profit += self.objets[ n ].profit
		self.liste[ n ] = 1
	
	# -----------------------------------------------------
	# retirer un objet du sac à dos
	# -----------------------------------------------------				
	def supprime_objet(self, n):
		"""
		Delete object from knapsack
		"""
		if self.liste[ n ] == 0:
			return
		self.poids -= self.objets[ n ].poids
		self.profit -= self.objets[ n ].profit
		self.liste[ n ] = 0
	
	# -----------------------------------------------------
	# Convertion un sac à dos en chaine
	# -----------------------------------------------------				
	def __str__(self):
		"""
		Transform object into string
		"""
		return "(poids=" + str(self.poids) + ",profit=" + str(self.profit) + "," + str(self.liste) + ")"

	# -----------------------------------------------------
	# Copie d'un sac à dos
	# -----------------------------------------------------
	def copy(self):
		"""
		Create copy of the object
		"""
		sac = Sac(self.objets, self.liste.copy())
		sac.poids = self.poids
		sac.profit = self.profit
		return sac




# ===================================================================
# Classe représentant un solveur de type heuristique
# ===================================================================
class SAD(object):
	"""
	This class is a solver based on a heuristic
	"""
	
	# -----------------------------------------------------
	# Constructeur
	# -----------------------------------------------------
	def __init__(self, poids_maximum, poids, profits):
		"""
		Constructor given maximum weight of knapsack, weights and
		profits of objects that can be put in the knaspsack.
		Objects are created in this class and are provided to the
		Sac class
		"""
		self.poids_maximum = poids_maximum
		self.profits = profits
		self.poids = poids

		self.nbr_objets = len(poids)
		self.objets = [ ]
		
		for i in range(len(poids)):
			objet = Objet(i+1, poids[i], profits[i])
			self.objets.append( objet )

		self.verbose = True
		
	# -----------------------------------------------------
	# Méthode heuristique basée sur le ratio profit / poids
	# -----------------------------------------------------
	def methode_heuristique(self):
		"""
		Heuristic-based method with the ratio profit / weight.
		Objects are ordered followinf this ratio and added
		to the knaspsack if they don't exceed the maximum
		weight
		"""
		print("=" * 40)
		print(" Début de la méthode heuristique ")
		print("=" * 40)
		
		# tri suivant le ratio, les objets les plus
		# intéressant sont en début de liste
		@@@...@@@
		
		
		print("-" * 30)
		print(" Objets triés suivant ratio  décroissant")
		print("-" * 30)
		for obj in self.objets:
			print(obj)

		
		# indice de l'objet
		i = 0
		# sac vide
		sac = Sac(self.objets, [0 for x in self.objets ])
		
		# pour chaque objet
		while i < len(self.objets):
			# si le poids maximum n'est pas dépassé
			# ajouter l'objet dans le sac
			@@@...@@@
			
			i += 1

		print("-" * 30)
		print(" Objetf inal      ")
		print("-" * 30)
		print( str( sac ) )

		return sac
	
	# -----------------------------------------------------
	# Affiche le résultat
	# -----------------------------------------------------	
	def print(self, sac):
		print("-" * 30)
		print(" Contenu du sac ")
		print("-" * 30)

		for i in range(len(self.objets)):
			if sac.liste[i] == 1:
				print(self.objets[i])
		print("profit_total=" + str(sac.profit), end=',')
		print("poids_total=" + str(sac.poids))

	# -----------------------------------------------------
	# Amélioration : suppression d'un élément puis tentative
	# d'en ajouter un autre
	# -----------------------------------------------------
	def ameliore(self, sac):
		"""
		Improvement of the knapsack : we remove each object
		in the knapsack and try to add other objects not
		present.
		"""
		print()
		print("=" * 40)
		print(" Méthode avec amélioration ")
		print("=" * 40)
		
		sacs_ameliores = []
		
		print(sac.liste)
		# pour chaque objet
		for k in range(len(sac.liste)):

			# supprimer le k-ieme objet
			if sac.liste[ k ] == 0:
				continue
			
			# créer une copie du sac sans l'objet qui doit être supprimé
			sac_allege = sac.copy()
			sac_allege.supprime_objet(k)
			
			# calcul du poids et profit du sac allege
			
			if self.verbose:
				print("-" * 30)
				print(" Sac avec objet supprimé ")
				print("-" * 30)
			   
				print("- on supprime ", self.objets[ k ])
				print("-" * 40 )
					
				print("- poids  allege=", sac_allege.poids)    
				print("- profit allege=", sac_allege.profit)  

			# on tente d'ajouter un nouvel objet s'il n'est pas
			# déjà dans la liste des objets
			@@@...@@@
				        
			sacs_ameliores.append( sac_allege )	        
				
         
		return sacs_ameliores 
	
# ===================================================================
# Programme principal
# ===================================================================

HELP_MESSAGE = """
Program arguments are:

-h or --help 
	to get this message

-q or --quiet 
	to remove verbose mode and avoid to display graphics
	
"""

sad = SAD(poids_maximum, poids, profits)

# gestion des arguments du programme
if len(sys.argv) >= 1:
	try:
		for i in range(1, len(sys.argv)):
			arg = sys.argv[i] 
			if arg == "-h" or arg == "--help":
				print( HELP_MESSAGE )

			elif arg == "-q" or arg == "--quiet":
				sad.verbose = False				

			else:
				raise ValueError("Unexpected argument")
				
	except:
		print("="*40)
		print(sys.exc_info()[1])
		print("="*40)
		print( HELP_MESSAGE )
		sys.exit(1)


print()
print("*" * 40)
print("Heuristique pour créer un sac")
print("*" * 40)


sac = sad.methode_heuristique()

print()
print("*" * 40)
print(" Amélioration")
print("*" * 40)

sac_ameliores = sad.ameliore(sac)

print()
for sac in sac_ameliores:
	sad.print( sac )

print()
sac_ameliores.sort(key= lambda x : x.poids)
for sac in sac_ameliores:
	print("- " + str(sac) )