Déterminer une relation de récurrence

[fatal_error]

je pense que t'as pas compris mon post de 21h19
donc toujours pareil tu prends un exemple simpliste et tu regardes

T=[1 2 3]
C=[5 6 2]
partons de la fin: donc pour i==2
V(2) va être appelée avec les symboles 5,6
V(2, 5) = max(nopickup, pickup) avec nopickup == 0+V(3,5) (en l'occurrence on dit V(3,..)==0) et pickup == B*3 + V(3,..)
V(2,6) = max( 0+ V(3,6), B*V(3,2))
mettons qu'au lieu d'écrire V on stocke v = [V(2,5), V(2,6)]

maintenant regardons en i==1
les symboles qui arrivent sont [5]
V(1,5) = max(0+V(2,5), B*2+V(2,6)) #point clé: en i==1, on se sert que du cache (i+1) idem le tableau de l'itération d'avant.

en i==0
V(0, ??) = max(0 + V(1, ??), B*1+V(1, 5))

ici, il faut que tu arrives dans ton algorithme à représenter le fait que pour une profondeur donnée, il y a le cas: "pas" de symboles arrivant car personne avant n'a pris d'élément (??).

[asse211]

[edit] Bonsoir, merci de ton temps, c'est la dernière question de mon TP je te rassure ... ^^

Je bloque complètement ... déjà qu'avec le top Down j'ai eu du mal, mais la le bottom up me donne du file à retordre.

J'ai fait le début de mon algo Bottom Up:

Code: Tout sélectionner

    def bottomup(self, t, c, a, b, i=0, lastvisited=-170):
        # Initialisation of track
        track = {(2000000, 2000000): 2000000}

        # Initialsation of keep
        keep = []

        for i in range(-1, -len(t) - 1, -1):
            track[i, lastvisited] = .....


Si je comprends bien :

-track[] : Mon dictionnaire qui contiendra la valeur maximale V[i]
-keep[] : L'indice "i" de mes emplacement visité pour obtenir un parcours maximal

J'ai réellement besoins d'un coup de pouce, du pseudo-code peut-être. Pour au moins attraper la logique que je ne vois absolument pas.

Encore une fois désolé pour mon manque de connaissance, mais je suis perdu ... j'y ai encore passé la soirée en vain

Merci par avance,

PS: je te met un exemple d'algorithme Bottom up pour un rendu de pièce de monnaie, classique comme problème :

Code: Tout sélectionner

def DPBUChange(S,X):
    track = [0]*(X+1)
    keep = [0]*(X+1)
    for x in range(1,X+1):
        mini = X+1
        for i in range(len(S)):
            if (S[i]<=x) and
            (1+track[x-S[i]]<mini):
                mini = 1+track[x-S[i]]
                coin = i
        track[x] = mini
        keep[x] = coin x,L = X,[]
    while x>0:
        L.append(S[keep[x]])
        x-=S[keep[x]]   
    return track[X],L
       
S=(1,2,5,10,20)
print(DPBUChange(S,11))


Le faite que l'on nu'utilise plus la récursivité ma perdu je crois ...

[fatal_error]

Code: Tout sélectionner

Def v(i):
keep= [0 for i in c]
Depth=n-1
while depth >i
Tmp=array()# depth-i+1
For k in range(i, depth)#all potential incoming symbols
ab = A if c[depth]==c[k] else B
#nopickup, pickup
tmp[k]=max(0+keep[k], ab*T[depth]+keep[depth])
Endfor
Keep=tmp
depth -=1
Endwhile
return max(0+keep[??],  B*T[i]+keep[i])
Enddef


depuis smartphone, dsl pour indentation
Approximatif sur les indices
Pas sur que le pseudo code taide plus mais bon sait on jamais

[asse211]

Hello,

Je me suis penché sur ton algo, voici ce à quoi je suis arrivé en fin de journée :

Code: Tout sélectionner

    def bottomup(self, t, c, a, b, i=-1):
        keep = [0] * len(c)
        depth = len(c) - 1

        while depth > i:
            tmp = [0] * (depth + 1)

            for k in range(i, depth):

                if c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

                tmp[k] = max(0 + keep[k], ab * t[i] + keep[depth])

            keep = tmp
            depth -= 1

        maxi = max(0 + keep[i], b * t[i] + keep[i])

        return maxi, keep

Pour l'exemple :

c = [2, 1, 1, 4, 4, 2]
t = [9, 7, 8, 7, 10, 7]
a = -2
b = 5

J'obtiens V[i] = 140 ... alors que je devrais obtenir 170. il ne me sort pas la solution optimale.

De plus quand je return keep[], il me faudrait les indices "i" des positions visitées pour obtenir les maximum V[i]

Pour l'exemple ci dessus, keep[] = 105 ....

Merci par avance de ton aide et bonne soirée.

[fatal_error]

hi,

ca doit probablement faire 3 fois au moins, mais je vais répéter encore:
- si ca marche pas pour ton T à 6 elems, regarde pour des T plus petits:

à toi de choisir tes T, tes C, la somme que tu attends, et de spécifier ce que ton algo doit retourner. Une fois que t'as spécifié tu le lances et tu corriges, ou pas (si il a fait le job correctement)
1) regarde pour T avec 1 seul élément, et pour B positif ou B négatif
2) regarde pour T avec deux elements, et C qui a les même symboles, ou pas
3) regarde pour T avec trois elements, et C qui a tous les même symboles (et joue avec les valeurs de T pour vérifier que l'algo est correcte)
4) regarde pour T avec trois elements, B<0, le premier elem à ignorer et les deux suivants à piocher pour maximiser la somme
etc...

le etc est tres important. je n'ai peut être pas tout couvert

[asse211]

Merci pour ton aide .. mais je n'arrive pas à debugger ce programme c'est impressionnant j'ai un manque de logique pour cette algorithme.

Je ne ferrais pas cet algo'

[fatal_error]

ben je sais pas trop ce que t'as débuggué, mais la première et plus basique des choses est:

1) regarde pour T avec 1 seul élément, et pour B positif ou B négatif

t=[1]
c=[1]
a=2
b=-5
qui doit te donner 0, or ton algorithm te retourne 2. Donc déjà avec un elem c'est faux.

les choix sont: 0 ou -5*1
que vaut maxi dans ton cas

Code: Tout sélectionner

    print(0 + keep[i], b * t[i] + keep[i])
    maxi = max(0 + keep[i], b * t[i] + keep[i])


conclusion: ta première opérande est mauvaise(2), ta deuxième aussi(-3).

si tu ecris 0+keep[-1], ca veut dire que tu dois avoir keep[-1]==0 (vu que tu ne pioches rien), or en sortie de ta boucle while, tu n'as pas keep[-1]==0 tu as keep==[2], idem keep[-1]==2
donc tu regardes ton while et tu regardes pourquoi keep est mal rempli

tu itères avec k==-1
c[k], pour k==-1, qu'est-ce que ca réprésente?
A priori t'es sensé itérer avec les symboles de c_0 à c_depth...
et soit dit en passant faut il inclure c_depth?

[asse211]

Je dirais que la boucle for permet d'itérer de l'arrière de mon tableau T vers la premier élément du tableau T à l'avant non ?

c[k] le dernier symbole de ma liste à l'arrière, la boucle for permet d’ailleurs itérer sur les symboles de cette liste c[] pour arriver à l'élément à l'indice c[0] non ?

Et je dirais qu'il ne faut pas inclure detph dans le range(), en utilisant plutôt "depth -1"

J'obtient donc après correction :

Code: Tout sélectionner

    def bottomup(self, t, c, a, b, i=-1):
        keep = [0] * len(c)
        depth = len(c) - 1

        while depth > i:
            tmp = [0] * (depth + 1)
            print(tmp)

            for k in range(i, depth - 1):

                if c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

                tmp[k] = max(0 + keep[k], ab * t[i] + keep[depth])

            keep = tmp
            depth -= 1

        maxi = max(0 + keep[i], b * t[i] + keep[i])

        return maxi, keep

Merci par avance

[fatal_error]

c[k] le dernier symbole de ma liste à l'arrière, la boucle for permet d’ailleurs itérer sur les symboles de cette liste c[] pour arriver à l'élément à l'indice c[0] non ?

C'est faux pour deux raisons:
1) tu ne veux pas du symbole à l'arriere (c'est même le contraire!! tu ne veux que les symboles à l'avant)
2) oui tu veux c[0] et de manière générale c[0]...c[depth...] (avec ... pour dire attention aux indices) si et seulement si le mec veut calculer la somme V0. Si il veut calculer la somme V3, tu veux du range(3, depth...))

Et je dirais qu'il ne faut pas inclure detph dans le range(), en utilisant plutôt "depth -1"

ok (mais attention, en python range n'inclue pas le dernier elem) donc si tu ecris range(1,3) tu n'as que 1 et 2 donc en fait ecrire range(1, depth) correspond à prendre les indices 1,..., depth-1 ce qui est bien l'effet escompté

--------------
Au cas où tu ne visualiserais pas très bien (notamment avec ton symbole à l'arrière??)

Code: Tout sélectionner

 T=[9, 7, 8, 7, 10, 7]
 C=[2, 1, 1, 4, 4,  2]
    |
    +-------------->V(5, 2)
       |
       +----------->V(5, 1)
       +----------->V(5, 1)
             |
             +----->V(5, 4)
                +-->V(5, 4)
                  ->V(5, _)


Pour V(5,2) ca signifie que à un moment tu as pioché 9, puis...tu n'as jamais rien pioché et ton dernier symbole est tonjours 2. Puis tu arrives sur T[5] et donc tu cherches V(5,2)

Tu construis V(5,2): max(0, A*7) A car C[5]==C[0]
Tu construis V(5,1): max(0, B*7) B car C[5]!=C[0]
Tu construis V(5,_): max(0, B*7) B car c'est le premier elem pioché (tout le monde auparavant n'a pas pioché)

Ensuite tu cherches à calculer V(4)

Code: Tout sélectionner

 T=[9, 7, 8, 7, 10, 7]
 C=[2, 1, 1, 4, 4,  2]
    |
    +----------->V(4, 2)
       |
       +-------->V(4, 1)
       +-------->V(4, 1)
             |
             +-->V(4, 4)
               ->V(4, _)


Tu construis V(4,2): max(0+V(5,2), B*10 + V(5,4)) B car C[4]!=C[0] et V(5,4) car comme on a pioché le dernier symbole est désormais 4
Tu construis V(4,1): max(0+V(5,1), B*10 + V(5,4)) B car C[4]!=C[1] et idem...
Tu construis V(4,4): max(0+V(5,4), A*10 + V(5,4)) A car C[4] == C[3]
Tu construis V(4,_): max(0+V(5,_), B*10 + V(5,4)) B car c'est le premier elem

...

Code: Tout sélectionner


 T=[9, 7, 8, 7, 10, 7]
 C=[2, 1, 1, 4, 4,  2]
    |
    +-->V(1, 2)
      ->V(1, _)


Tu construis V(1,2): max(0+V(2,2), B*7+V(3,1))
Tu construis V(1,_): max(0+V(2,_), B*7+V(3,1))

Et enfin tu construis ...

Code: Tout sélectionner

V(0, _) = max(0+V(1,_), B*9+V(1,2))


A partir de là ya plus de magie...
tu calcules tes tableaux keep __à la main__
a chaque itération tu regardes s'ils sont remplis correctement

[asse211]

Parfait donc pour "i" je l'initialise à i=-1 et ensuite je n'inclus pas depth dans le range()

Soit :

Code: Tout sélectionner

def bottomup(self, t, c, a, b, i=-1):

Code: Tout sélectionner

for k in range(i, depth):

Déjà la dessus nous sommes d'accord ?

Je suis sur le reste de ton explication, qui je pense m'aide bien a visualiser les choses ! Merci, je te tiens au courant

[asse211]

J'ai aussi rajouté une troisième condition au moment de l'affectation de a ou b tel que :

Code: Tout sélectionner

                if depth == k:
                    ab = b
                elif c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

En effet lorsque depth == k, c'est à dire qu'aucun élément n'avait été pioché, donc pas de symbole lastivisted, il faut faire "b * T[i]" Tu confirmes ?

[fatal_error]

Code: Tout sélectionner

    for k in range(i, depth):

range(_, depth) ok
mais range(i, _) ko. ca n'a aucun sens de partir de -1, cf mes deux derniers postes

Code: Tout sélectionner

                if depth == k:
                    ab = b
                elif c[depth] == c[k]:
                    ab = a
                else:
                    ab = b


dans l'idée c'est correct, mais vu que k ne vaut plus depth...

[asse211]

Carrément !! et j'ai bien vite corrigé ça !
Je part pour i = 0 avec depth = 0

Sinon je ne commençais jamais par l'a case d'indice "0"

Je vérifie tout mon algo' ... pour le moment je ne trouve pas d'erreur pourtant le résultat de fin est faux je creuse

Encore merci de temps, bonne soirée

[asse211]

[edit]Après vérification de l'exemple pour lequel tu as faits les schémas pour chaque étape je trouve bien au final V[i] = 170 !

Voici l'algorithme après quelques corrections :

Code: Tout sélectionner

    def bottomup(self, t, c, a, b, i=-1):
        keep = [0] * len(c)
        depth = len(c) - 1

        while depth > i:
            tmp = [0] * (depth + 1)

            for k in range(i + 1, depth + 1):

                if depth == k:
                    ab = b
                elif c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

                tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

            keep = tmp
            depth -= 1

        return keep

Or pour l'exemple :

t = [5, 2, 10, 4, 8]
c = [1, 5, 5, 5, 2]
a = -5
b = 8

Je tombe sur V[i] = 24 ....

Une idée de ? Je pense que c'est quand A est négatif qu'il y a un problème ....

Merci par avance Tes schémas mon permis de comprendre le fonctionnement ! PARFAIT

[fatal_error]

déjà bvo ca a plus de look
et 2, je pense que tu fatigues, j'ai copié comme un cochon ton code et je trouve [184] (qui est bien le résultat attendu: 8*5+8*10+8*8)

https://trinket.io/python/61cc6f3a90

[asse211]

Merci

oui oui je fatigue ! je me suis trompé dans l'exemple :

essaye avec celui-ci :

t = [3, 9, 2, 7, 3, 1]
c = [2, 2, 5, 4, 2, 1]

a, b = 2, -5

Merci par avance

[fatal_error]

c'est une erreur de sémantique:
dans ton max tu as:
max(0+keep[k]) qui signifie: "laisse passer le symbole et ne prends rien"
sauf que pour i==-1, tu itères le premier k avec le symbole keep[0]
sauf que pour le premier element, tu devrais avoir max(0 + keep['_'], ..)
où est-ce que V(1, '_') est stocké dans keep?

[asse211]

[edit]Humm je vois un petit peux ...

Je dirais que "V(1, '_')" est stocké à l'indice : keep[1] nan ?

Mais comment je peux le récupérer quand il reste que depth == 1 ? Je ne vois pas du tout ...

Surtout que dans le cas que je t'ai présenté il ne s'agit pas du max .. c'est pour ça qu'il ne le trouve pas, et qu'il trouve 24 au lieu de 9

Merci par avance

[fatal_error]

Si tu veux acceder a keep[1] au lieu de de keep[k] pour un depth donné... Ben tu mets un if depth==

Tu noteras que tu te fais en fait punir par ta boucle for.
Tu iteres sur tous les symboles(avant) PLUS le symbole courant k==depth, et en loccurrence pour ce symbole courant tes obligé de faire un traitement specifique... Donc autant etre semantiquement consistent: tu fais ton for que sur les symboles avant et tu rajoutes apres le cas du V(depth, _) (donc en dehors du for), ce qui est la meme chose que toi sauf que ds ton implen actuelle cest masqué...

Si tu le fais proprement tu constates alors trivialement que V(depth,_) est en fait a la fin de ton tableau keep et quen loccurrence tu peux calculer tmp[-1]=max(keep[-1], ...).

Par rapport a 24 et 9, la difference est -15==-5*3 ca ressemble pas mal au fait qu a un moment tas pas pris le bon elem ds le max... Pe que fixer ton algo ne resoudra pas ton pb (mais un peu quand meme : ) )

[asse211]

[edit]Merci pour ton aide,

j'obtiens l'algorithme suivant :

Code: Tout sélectionner

    def bottomup(self, t, c, a, b, i=-1):
        track = [0] * len(c)
        depth = len(c) - 1

        while depth > i:
            tmp = [0] * (depth + 1)

            for k in range(i + 1, depth + 1):

                if depth == k:
                    ab = b
                elif c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

                if depth == 0 and k == 0:
                    tmp[k] = ab * t[depth] + track[k]
                else:
                    tmp[k] = max(0 + track[k], ab * t[depth] + track[depth])

            track = tmp
            depth -= 1

        return track

En ce qui concerne le stockage des indices visités pour obtenir V[i] ... comment puis-je faire ça ? Je n'arrive pas à déterminer quand stocker l'indice "k" dans un tableau, pour dire que c'est la case visiter pour obtenir V[i] au final.

Merci par avance,