Bonjour,

J'ai écris une fonction en Python dont le but est de, à partir une liste ordonnée d'entier positifs, construire un entier positif à partir d'additions d'une manière optimale, mais je ne comprends pas du tout le résultat que j'obtiens. Le problème n'est même pas s'il me donne un résultat exact ou non.
Le code est :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
def choix_elements(liste,max):
    n=len(liste)
    l=[-float('inf')]*(n+1)
    for i in range(n):
        l[i+1]=liste[i]
    matrice=[[0]*(max+1) for i in range(n+1)]
    matrice_des_elements=[[[0]*n]*(max+1) for i in range(n+1)]
    for i in range(n+1):
        for j in range(max+1):
            if j==0:
                matrice[i][j]=0
            elif i==0:
                matrice[i][j]=float('inf')
            else:
                x=0
                y=0
                if j-l[i]>=0:
                    y=1+matrice[i][j-l[i]]
                else:
                    y=float('inf')
                if i>=1:
                    x=matrice[i-1][j]
                else:
                    x=float('inf')
                if min(x,y)==y:
                    matrice_des_elements[i][j]=matrice_des_elements[i][j-l[i]]
                    matrice_des_elements[i][j][i-1]+=1
                if min(x,y)==x:
                    matrice_pieces[i][j]=matrice_pieces[i-1][j]
                matrice[i][j]=min(x,y)
      return matrice_des_elements
Alors, le but du code final du code est de trouver le nombre minimal d'éléments dans la liste liste pour construire max à partir d'additions, et de donner ces éléments. Alors pour ce faire, il va trouver ce nombre minimal pour tout élément j inférieur ou égal à max en partant de 0 (max est un entier strictement positif), et à chaque fois avec un seul élément de la liste des éléments. Ainsi, à chaque fois pour construire j on va voir j-l[i] (on a dit qu'on travaillait avec un seul élément dans la ligne i), car si on construit de manière optimale j-l[i] alors il ne resterait qu'à rajouter l[i] comme élément pour trouver j. Mais, il faut comparer avec la manière dont on a obtenu j en ayant utilisé que les éléments de l[:i].

Le résultat que j'obtiens est le suivant pour choix_elements([1,7,23],28) :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
[[[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, 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, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]],
 [[28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4]],
 [[0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0]],
 [[0, 0, 1],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0],
  [28, 18, 4],
  [0, 0, 1],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [28, 18, 4],
  [0, 4, 0]]]
Ce que je trouve bizarre. Car déjà si j==0 alors je devrais avoir des [0,0,0]. Car si j==0 je ne fais que modifier matrice (dont j'en aurais besoin plus tard).

J'espère que vous pourrez m'aider à comprendre d'où vient le problème. J'ai analysé et re-analysé le code mais je ne trouve vraiment pas d'où la première colonne n'est pas que des [0,0,0].

Merci d'avance.