Measure with defective jugs ThreeJugs.java
public static boolean checkFeasible(List<Jug> jugs, int L, int H) {
Set<Pair<Integer, Integer>> cache = new HashSet<>();
return checkFeasibleHelper(jugs, L, H, cache);
}
private static boolean checkFeasibleHelper(List<Jug> jugs, int L, int H,
Set<Pair<Integer, Integer>> c) {
if (L > H || c.contains(new Pair<>(L, H))
|| (L < 0 && H < 0)) {
return false;
}
// Checks the volume for each jug to see if it is possible.
for (Jug j : jugs) {
if ((L <= j.low && j.high <= H) || // Base case: j is contained in [L, H].
checkFeasibleHelper(jugs, L - j.low, H - j.high, c)) {
return true;
}
}
c.add(new Pair<>(L, H)); // Marks this as impossible.
return false;
}
public static class Jug {
public int low, high;
public Jug() {
}
public Jug(int low, int high) {
this.low = low;
this.high = high;
}
}
