private static void zyva (int d[], int m, int i, int [] r) { if (d[i] == 1) { r[i] = m ; dump(System.out, d, r) ; } else { int di = d[i] ; int max = m/d[i] ; for (int j = 0 ; j <= max ; j++) { r[i] = j ; zyva(d, m-j*di, i+1, r) ; } } } static void tous(int [] system, int m) { zyva(system, m, 0, new int[system.length]) ; } |
private static int minCard ; private static int [] minR ; private static void check(int card, int [] r) { if (card < minCard) { minCard = card ; for (int i = 0 ; i < r.length ; i++) minR[i] = r[i] ; } } private static void look(int [] d, int m, int i, int card, int [] r) { int di = d[i] ; if (di == 1) { r[i] = m ; check(card + m, r) ; } else { int max = m/di ; for (int j = 0 ; j <= max ; j++) { r[i] = j ; look(d, m-j*di, i+1, card+j,r) ; } } } static int [] exhaustif(int [] system, int m) { int len = system.length ; minR = new int [len] ; minCard = Integer.MAX_VALUE ; look(system, m, 0, 0, new int [len]) ; return minR ; } |
look(d, m-j*di, i+1, card+j,r) ; |
look(d, m, i+1, card+j,r) ; m -= di ; // Pour m = m - di |
private static void lookOpt(int [] d, int m, int i, int card, int [] r) { int di = d[i] ; if (card < minCard && di*(minCard-card) >= m) { if (di == 1) { r[i] = m ; check(card + m, r) ; } else { int max = m/di ; for (int j = max ; j >= 0 ; j--) { r[i] = j ; lookOpt(d, m-j*di, i+1, card+j,r) ; } } } } static int [] exhaustifOpt(int [] system, int m) { int len = system.length ; minR = glouton(system, m) ; minCard = card(minR) ; lookOpt(system, m, 0, 0, new int [len]) ; return minR ; } static int card(int [] t) { int r = 0 ; for (int i = 0 ; i < t.length ; i++) r += t[i] ; return r ; } |