Competitions » CodeFu Shortest Solution » Shortest 1 » Problem 400

Problem 400

Problem description here

This is the standard knapsack problem, with addition that we need to return the coins that produce a certain sum.
The problem is for sure a challenging one, as we should implement the coin string creating during the dynamic programming pass.

Here is the final solution:

<p>public class KeepTheChange {
  int c;
  public String getOptimumChange(int a, int[] t) {
    String[] z = new String[a + 1];  
    z[a] = "IMPOSSIBLE";
    int[] m = new int[a + 1];
    for (int b : t)
      for (z[c = b] = b + "", m[c] = a; c <= a ; c++) 
        if (m[c] < m[c - b]) { 
          m[c] = m[c - b] - 1;
          z[c] = b + "," + z[c - b];
        }
    return z[a];
  }
}</p>

Highlights

z[c = b] = b + "" initializes c and z[c] at the same time
the solution constructs all the best solutions up to 'a' and then just returns the value if it exists

Competitions
- CodeFu 2023
  - Final Round