new int[m+1]
).M(0) = 0, M(n) = 1+ |
|
M(n-di) |
static int [] dynamiqueCard(int [] d, int m) { int k = d.length ; int [] card = new int [m+1] ; ••• int [] esp = new int [m+1] ; card[0] = 0 ; // Inutile en Java for (int n = 1 ; n <= m ; n++) { int r = m+1 ; int i ; for (i = 0 ; d[i] > n ; i++) ; for (; i < k ; i++) { int di = d[i] ; if (card[n-di]+1 < r) { r = card[n-di]+1 ; ••• esp[n] = i ; } } card[n] = r ; } return card ; } |
int r = new int[k] ; while (m > 0) { int i = esp[m] ; r[i]++ ; // Pour r[i] = r[i]+1 ; m -= d[i] ; } |
static int [] dynamique(int [] d, int m) { int k = d.length ; int [] card = dynamiqueCard(d, m) ; int [] r = new int[k] ; while (m > 0) { int c = card[m] ; int i ; for (i=0 ; d[i] > m ; i++) ; for ( ; ; i++) { int di = d[i] ; if (card[m-di] == c-1) { m -= di ; r[i]++ ; break ; } } } return r ; } |
for ( ; ; ) { … } |
static int [] dynamique(int [] d, int m) { int k = d.length ; int [] card = dynamiqueCard(d, m) ; int [] r = new int[k] ; while (m > 0) { int c = card[m] ; for (int i = k-1 ; ; i--) { // Pas de condition int di = d[i] ; if (card[m-di] == c-1) { // Car di tel que card[m-di] == c-1 existe m -= di ; r[i]++ ; break ; } } } return r ; } |