Please enable JavaScript.

Coggle requires JavaScript to display documents.

M17 - Coggle Diagram

- - - - Algorithm: int CoinRow(C[1..n])
        F[0], F[1] <- 0, C[1];
        for int i <- 2 to n do {
        F[i] <- max(C[i] + F[i - 2] , F[i-1]); }
        return F[n];
  - - - Algorithm: int ChangeMaking(D[1..m], n)
        F[0] <- 0;
        for i <- 0 to n do{
        temp, j <- infinity, 1;
        while j <= m && i >= D[j] do{
        temp <- min(F[i - D[j]], temp);
        j <- j + 1; }
        F[i] <- temp + 1; }
        return F[n];
  - - - Bottom-Up
        
        Algorithm: int KnapSack(n, W, w[1..n], v[1..n], F[0..n, 0..W])
        for i <- 0 to n do {
        for j <- 0 to W do{
        if i = 0 || j = 0 then F[i][v] <- 0;
        else if w[i] <= j then
        F[i][j] <- max(F[i - 1][j], v[i] + F[i - 1][j - w[i]]);
        else
        F[i][j] <- F[i - 1][j]; }
        }
        return F[n][W];
      - Top-Down
        
        Algorithm: int KnapSack(i, j, w[1..n], v[1..n], F[0..n, 0..W])
        if F[i, j] < 0 then {
        if j < w[i] then value <- KnapSack(i-1, j, w, v, F);
        else {
        value <- max(KnapSack(i-1, j, w, v, F), v[i] + KnapSack(i-1, j-w[i], w, v, F)); }
        F[i, j] <- value;
        }
        return F[i, j];