[PYTHON] Je pense que la limite du sac à dos n'est pas le poids mais le volume w_11 / 22update
Bonsoir (* ´ω ｀) Merci pour votre soutien m (_ _) m
J'ai défié le fameux sac à dos. En regardant en diagonale le code d'un expert J'ai juste réfléchi à ce que je voulais faire.
KnapSack.py
class Item:
def __init__(self,w=0,p=0):
self.weight=w
self.price=p
items = [ Item(300,400), Item(500,250), Item(200,980),
Item(600,340), Item(900,670), Item(1360,780),
Item(800,570), Item(250,800) ]
def knapsack(i, w):
if i==len(items):
return 0
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Val_sum0 = knapsack(i+1, w)
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price
return max(Val_sum0,Val_sum1)
p = knapsack(0, 1200)
print("MAXIMUM TOTAL PRICE is",p)
Que vous posiez vos bagages ou non Considérez le nombre de tentatives (nombre de tentatives) comme i. Heureusement, les articles alignés sont limités, C'est un problème de trouver la valeur maximale dans une condition donnée.
Laisser le sac à dos retourner à 0 en essayant jusqu'à la fin. Promesse récursive, définissez ceci dans le cas de base.
KnapSack.py
def knapsack(i, w):
if i==len(items):
return 0
Cependant, cela ne fait pas l'histoire, donc Dans le processus, nous ajouterons le prix de l'article.
Bien sûr, cela n'ajoute pas indéfiniment. La valeur maximale doit être trouvée dans le poids défini. Par conséquent, chaque fois que vous ajoutez un article, soustrayez le poids de l'article du poids maximum défini. Lorsque w --items [i] .weigh <0, J'ai renoncé à ajouter des articles [i] car il dépasse la limite de poids. Incrémentez i pour essayer d'ajouter l'élément suivant.
KnapSack.py
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Félicitations, comme mentionné ci-dessus
- Le nombre d'essais i est inférieur ou égal au nombre d'éléments
- Ne dépassez jamais la limite de poids Ce n'est qu'après avoir effacé les conditions que vous déciderez d'ajouter ou non des éléments. Vous pouvez y réfléchir.
KnapSack.py
Val_sum0 = knapsack(i+1, w)#Ne pas ajouter
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price #ajouter
return max(Val_sum0,Val_sum1)#Lequel est plus gros?
Dans la description ci-dessus, j'étais accro à Val_sum1 = sac (i + 1, w - articles [i] .poids) + articles [i] .prix Ajouter des articles.Prix au sac à dos? Quelle? (ﾟ Д ﾟ) était.
Mais quand on y pense, le sac à dos est un processus récursif, donc il finit par tomber dans le cas de base. C'est vrai, ce sera 0. Par conséquent, seul le résultat de l'empilement items.price sera retourné.
Ensuite, puisque la description ci-dessus est ** recherche complète **, Des calculs en double ont été inclus. Je vais le réduire.
Cependant, c'était possible, mais cela peut être subtil (rires)
knapsack.py
class Item:
def __init__(self,w=0,p=0):
self.weight=w
self.price=p
items = [ Item(300,400), Item(500,250), Item(200,980),
Item(600,340), Item(900,670), Item(1360,780),
Item(800,570), Item(250,800) ]
def knapsack(i, w):
if memo[i][w]:#Vérifiez s'il y a quelque chose dans la cellule correspondante du mémo.
return memo[i][w]#Valeur renvoyée une fois saisie, réduction du calcul!!
if i==len(items):
return 0
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Val_sum0 = knapsack(i+1, w)
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price
memo[i][w] = max(Val_sum0,Val_sum1) #Fait une note!!
return memo[i][w]#Renvoie la valeur que vous avez notée
wgoal = 700
memo = [[[]for k in range(wgoal + 1)] for l in range(len(items)+1)] #Fabriqué un vaste bloc-notes(Lol)
p = knapsack(0,wgoal)
print("MAXIMUM TOTAL PRICE is",p)
Ce que j'ai appris jusqu'à présent, c'est de préparer un mémo C'est un défi de réduire le calcul en appelant ce qui a été calculé dans le passé.
Cependant, le mémo que j'ai préparé cette fois est trop vaste (rires). Ce que j'écris maintenant Notez le prix maximum pour le poids à un certain nombre d'essais. S'il pèse plusieurs centaines, l'échelle du mémo à préparer sera grande. Erreur de réglage du problème !! (* noωno)
À propos, il existe également une méthode qui n'utilise pas la récurrence.
knap_dp.py
N = 8 #number of backs
w =[300, 500, 200, 600, 900, 1360, 800, 250]
v =[400, 250, 980, 340, 670, 780, 570, 800]
wgoal = 700
memo = [[0]*(wgoal+1)for l in range(N+1)]
for i in range(N):
for j in range(wgoal+1):
if j < w[i]:
memo[i+1][j] = memo[i][j]
else:
memo[i+1][j] = max(memo[i][j],memo[i][j-w[i]]+v[i])
print("MAXIMUM TOTAL PRICE is",memo[N][wgoal])
La tenue était très rafraîchissante. J'ai essayé différents poids avec un traitement récursif, Passer à l'instruction for et à la i-ème tentative J'écris tous les poids (cela semble s'appeler DP).
Je ne peux pas nier le sentiment que je lis et écris et que je bouge d'une manière ou d'une autre. Je vais essayer de créer une image avec un peu plus local (* ´ 艸 ｀).
-11/22_update-------------------------------------------------------------
En réfléchissant à l'erreur de définition du problème l'autre jour, Je l'ai changé un peu, facilement (rires)
knap_dp.py
N = 3 #number of backs
w =[3, 4, 5]
v =[30, 50, 60]
wgoal = 8
memo = [[0]*(wgoal+1)for l in range(N+1)]
for i in range(N):
for j in range(wgoal+1):
if j < w[i]:
memo[i+1][j] = memo[i][j]
else:
memo[i+1][j] = max(memo[i][j],memo[i][j-w[i]]+v[i])
print(f"i={i},j={j}")
for k in memo:
print(k)
print()
print("MAXIMUM TOTAL PRICE is",memo[N][wgoal])
Je vais l'exécuter pour le moment.
Résultat d'exécution.py
i=0,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
i=2,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 0, 0, 0, 0]
i=2,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 0, 0, 0]
i=2,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 0, 0]
i=2,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 0]
i=2,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 90]
MAXIMUM TOTAL PRICE is 90
Une personne qui peut être montrée et comprise autant est un génie.
Je suis une personne ordinaire, je vais donc l'organiser en créant une image.
Tout d'abord, imaginez un mémo que vous avez préparé vous-même.
w est le poids. Il augmentera progressivement vers wgoal.
Suivons le programme.
Allons-y dong dong.
Maintenant que nous savons ce que nous voulons faire, nous allons rassembler le reste de N = 0.
Essayons N = 1 avec la même idée.
J'essaierai également N = 2.
Je vois, 90 est le maximum.
J'ai réussi à suivre le code,
Fais-tu une telle table dans ta tête? Tout le monde est un génie (ﾟ Д ﾟ)
Je pratique peu à peu et je vais régulièrement (..) φ memo memo
Recommended Posts