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

  1. Le nombre d'essais i est inférieur ou égal au nombre d'éléments
  2. 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. 図1.PNG Suivons le programme. 図2.PNG Allons-y dong dong. 図3.PNG 図4.PNG 図5.PNG 図6.PNG Maintenant que nous savons ce que nous voulons faire, nous allons rassembler le reste de N = 0. 図7.PNG Essayons N = 1 avec la même idée. 図8.PNG J'essaierai également N = 2. 図9.PNG 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

Je pense que la limite du sac à dos n'est pas le poids mais le volume w_11 / 22update
J'ai vérifié le contenu du volume du docker
Le modèle de projet Python auquel je pense.
La valeur de pyTorch torch.var () n'est pas distribuée
Quand vous pensez que la mise à jour de ManjaroLinux est étrange
Je sais, mais je ne peux pas m'arrêter - Python est une collection d'erreurs courantes
J'ai fait réfléchir AI aux paroles de Genshi Yonezu (pré-traitement)
J'ai essayé d'agrandir la taille du volume logique avec LVM
J'ai fait réfléchir AI aux paroles de Genshi Yonezu (implémentation)
Si la précision du test PCR est mauvaise, pourquoi ne pas répéter le test?
Je veux afficher le nombre de num_boost_round lorsque early_stopping est appliqué à l'aide du rappel XGBoost (non atteint)