Advanced Algorithms: Dynamic Programming - Coin Row Example

coin_row.dart

// Advanced Algorithms: Dynamic Programming

// GitHub: https://gist.github.com/Esgrima/4a744b79077da2e43ba00935dca89313
// DartDevPad: https://dartpad.dev/4a744b79077da2e43ba00935dca89313

import 'dart:math' as math;

class CoinRow {
  // Coin-row problem: There is a row of n coins whose values are some
  // positive integers c1, c2, . . . , cn, not necessarily distinct. The goal is to pick up the
  // maximum amount of money subject to the constraint that no two coins adjacent
  // in the initial row can be picked up.
  static int getMaxValue(List coins) {
    List<int> running = [0, coins[0]];

    for (var i = 2; i <= coins.length; i++) {
      running.add(math.max(coins[i - 1] + running[i - 2], running[i - 1]));
    }

    return running[running.length - 1];
  }

  // This version returns the set of coins that contribute to the max value
  // Avoids backtracking and recomputation. Does it along the way.
  static Set<int> getMaxSet(List coins) {
    List<int> running = [0, coins[0]];
    Set<int> desired_coins = {};

    for (var i = 2; i <= coins.length; i++) {
      if (coins[i - 1] + running[i - 2] > running[i - 1]) {
        desired_coins.add(coins[i - 1]);
        running.add(coins[i - 1] + running[i - 2]);
      } else {
        desired_coins.add(coins[i - 2]);
        running.add(running[i - 1]);
      }
    }
    return desired_coins;
  }
}

void main() {
  List<int> coins = [5, 1, 2, 10, 6, 2];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));

  //   The following proves that the optimal solutions of the subinstances
  //   are very likely to be part of the superset

  coins = [1];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));

  coins = [1, 8];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));

  coins = [1, 8, 4];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));

  coins = [1, 8, 4, 10];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));

  coins = [1, 8, 4, 10, 5];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));

  coins = [1, 8, 4, 10, 5, 9];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));

  coins = [1, 8, 4, 10, 5, 9, 6];

  print(CoinRow.getMaxValue(coins));
  print(CoinRow.getMaxSet(coins));
}

https://dartpad.dev/4a744b79077da2e43ba00935dca89313