diff options
Diffstat (limited to 'Practical2/src')
| -rw-r--r-- | Practical2/src/nl/camilstaps/cs/CheckoutHelper.java | 45 |
1 files changed, 40 insertions, 5 deletions
diff --git a/Practical2/src/nl/camilstaps/cs/CheckoutHelper.java b/Practical2/src/nl/camilstaps/cs/CheckoutHelper.java index 5ad7d2d..5688cf0 100644 --- a/Practical2/src/nl/camilstaps/cs/CheckoutHelper.java +++ b/Practical2/src/nl/camilstaps/cs/CheckoutHelper.java @@ -12,15 +12,50 @@ class CheckoutHelper { public CheckoutHelper() { } + private static int round(int cents) throws IllegalArgumentException { + switch (cents % 5) { + case 0: return cents; + case 1: return cents - 1; + case 2: return cents - 2; + case 3: return cents + 2; + case 4: return cents + 1; + } + throw new IllegalArgumentException("Incorrect number of cents."); + } + public int minimumPayment(int dividers) { - int sum = minimal_price; - for (int n : products) - sum += n; - return sum; + int minimums[][] = new int[products.size() + 1][dividers + 1]; + int last[][] = new int[products.size() + 1][dividers + 1]; + for (int p = 0; p <= products.size(); p++) { + for (int d = 0; d <= dividers; d++) { + if (p == 0) { + minimums[p][d] = 0; // No products + last[p][d] = 0; + } else if (d == 0) { + int sum = 0; + for (int p2 = 0; p < products.size() && p2 < p; p2++) + sum += products.get(p2); + minimums[p][d] = round(sum); // no dividers + last[p][d] = sum; + } else { + int try1 = minimums[p-1][d] - round(last[p-1][d]) + round(last[p-1][d] + products.get(p-1)); // don't place a divider + int try2 = minimums[p-1][d-1] + round(products.get(p-1)); // place a divider + if (try1 < try2) { + minimums[p][d] = try1; + last[p][d] = last[p-1][d] + products.get(p-1); + } else { + minimums[p][d] = try2; + last[p][d] = products.get(p-1); + } + } + } + } + + return minimal_price + minimums[products.size()][dividers]; } public void addProduct(int price) { - int has_to_pay = price / 5; + int has_to_pay = (price / 5) * 5; int rest = price % 5; minimal_price += has_to_pay; |