Cracking the Piggy Bank Puzzle: A Java Adventure in Dynamic Programming

Hey there, intrepid coders! Today, we're diving into a piggy bank heist… of the intellectual kind, of course! We'll be using a powerful technique called Dynamic Programming (DP) to crack the code of a mischievous piggy bank and unlock its hidden treasures. Buckle up, because this adventure requires both logic and a dash of mathematical magic.

Imagine a piggy bank with compartments numbered 1 to N. Each compartment holds a certain amount of coins. Your mission is to maximise the total coins you can collect by following these two rules:

1. You can only start at compartment 1 and move rightward, collecting all the coins in a compartment before proceeding.
2. You can either skip a compartment (earning you 0 coins) or rob a compartment, but robbing two consecutive compartments is forbidden.

This might seem tricky, but DP comes to the rescue! It breaks down the problem into smaller, overlapping subproblems and cleverly stores the solutions, saving you from redundant calculations. Think of it like mapping a treasure hunt – each solution to a subproblem guides you towards the bigger prize.

class PiggyBankBreaker {

    private final int[] coins; // Array storing coins in each compartment (1-indexed)
    private final int[] maxCoins; // DP array to store max achievable coins at each position (0-indexed)

    public PiggyBankBreaker(int[] coins) {
        this.coins = coins; // Copy original coin values
        this.maxCoins = new int[coins.length + 1]; // Allocate DP array with space for starting point (index 0)
    }

    public int crackPiggyBank() {
        // Base case: No coins at starting point
        maxCoins[0] = 0;

        // Loop through each compartment from index 1 (inclusive)
        for (int i = 1; i <= coins.length; i++) {
            // Option 1: Rob current compartment + max from 2 positions back (non-consecutive)
            int robCurrent;

            // Check if robbing current is even possible (avoid accessing coins[-1])
            if (i >= 3) {
                robCurrent = coins[i - 1] + maxCoins[i - 3];
            } else {
                // Default to skipping for initial positions where robbing isn't valid
                robCurrent = 0;
            }

            // Option 2: Skip current compartment and take max from previous position (consecutive)
            int skipCurrent = maxCoins[i - 1];

            // Choose the option that yields more coins
            maxCoins[i] = Math.max(robCurrent, skipCurrent);
        }

        // Return the maximum achievable coins from the last compartment
        return maxCoins[coins.length];
    }

    public static void main(String[] args) {
        // Example piggy bank with coins
        int[] coins = {2, 3, 1, 4, 5, 7, 10};

        PiggyBankBreaker breaker = new PiggyBankBreaker(coins);
        int maxLoot = breaker.crackPiggyBank();
        System.out.println("Maximum amount you can collect: " + maxLoot);
    }
}

This Java code solves the piggy bank problem, where you maximise the coins collected while adhering to two rules:

1. Start at compartment 1 and move rightward, collecting all coins in each compartment.
2. You can either skip or rob a compartment, but not two consecutive compartments.

The code utilises Dynamic Programming (DP) to efficiently solve this problem by breaking it down into smaller, overlapping subproblems. Here's a breakdown of the key aspects:

• The method calculates the maximum coins achievable from any starting point.
• Base case: maxCoins[0] = 0 since no coins are earned before starting.
• Loop: Iterates through each compartment (index 1 to length).
• Rob current option:
  • Calculates robCurrent by adding the current coin value (coins[i - 1]) to the maximum coins achievable two positions back (maxCoins[i - 3]).
  • Fix: A conditional statement (i >= 3) ensures this calculation only happens for valid positions (avoiding coins[-1] access).
  • Otherwise, robCurrent is set to 0, mimicking skipping the compartment for initial positions.
• Skip current option: Simply takes the maximum coins from the previous position (maxCoins[i - 1]).
• Comparison: Chooses the maximum value between robCurrent and skipCurrent and stores it in maxCoins[i]. This ensures the optimal decision is recorded for future subproblems.
• Final result: The last element maxCoins[coins.length] represents the maximum achievable coins from the starting point (compartment 1).

Knapsack Problem implementation in Java

Imagine a hiker's backpack (the knapsack) with limited space (capacity).

They have a collection of items, each with a value (usefulness) and a weight (space it occupies).

The goal is to fill the backpack with the most valuable combination of items, without exceeding its weight capacity.

Visualizing the Items

Item 1:  (value 60, weight 10)
Item 2:  (value 100, weight 20)
Item 3:  (value 120, weight 30)

The Knapsack

Decision-Making

• Can't fit all items directly (total weight 60).
• Optimal choice would be to put these items in the bag
  
• Item: {value: 120, weight: 30}
• Item: {value: 100, weight: 20}

Optimal Solution

KNAPSACK  (capacity 50)
     (value 120, weight 30)

Key Points

• Knapsack represents a resource constraint (limited capacity).
• Items represent choices with associated values and constraints (weight).
• Goal is to maximize value within the constraint.
• Often involves trade-offs and strategic decision-making.

In formal language, given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, find the subset of items that maximizes the total value while fitting within the weight capacity.

Dynamic Programming Approach

1. Create a table dp:

   • Dimensions: (n + 1) x (W + 1), where n is the number of items and W is the knapsack capacity.
   • dp[i][w] stores the maximum value achievable using items up to the i-th item and with a maximum weight of w.

2. Fill the table:

   • Base cases:
     • dp[0][w] = 0 for all w (no items, value is 0).
     • dp[i][0] = 0 for all i (zero weight capacity, value is 0).
   • Recursive formula:
     • dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w (Choose between including or excluding the i-th item)
     • dp[i][w] = dp[i-1][w] otherwise (Item cannot be included due to weight constraint)

3. Solution:

• The maximum value is dp[n][W] (using all items with the knapsack capacity).
• Backtrack to find the selected items.

import java.util.ArrayList;
import java.util.List;

public class Knapsack {

    public static List knapsack(List items, int capacity) {
        int[][] dp = new int[items.size() + 1][capacity + 1];

        // Build table dp[][] in a bottom-up manner
        for (int i = 0; i <= items.size(); i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (items.get(i - 1).weight <= w) {
                    dp[i][w] = Math.max(items.get(i - 1).value + dp[i - 1][w - items.get(i - 1).weight], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // Reconstruct the solution
        List selectedItems = new ArrayList<>();
        int i = items.size(), w = capacity;
        while (i > 0 && w > 0) {
            if (dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(items.get(i - 1));
                w -= items.get(i - 1).weight;
            }
            i--;
        }

        return selectedItems;
    }

    public static void main(String[] args) {
        List items = new ArrayList<>();
        items.add(new Item(60, 10));
        items.add(new Item(100, 20));
        items.add(new Item(120, 30));
        int capacity = 50;

        List selected = knapsack(items, capacity);
        System.out.println("Selected items: " + selected);
    }

    public static class Item {
        int value;
        int weight;

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Item: {value: " + value + ", weight: " + weight + "}";
        }
    }
}

Explanation of code

1. Item Class:

• Represents an item with its value and weight.

2. knapsack() Method:

• Takes a list of items and a knapsack capacity as input.
• Uses dynamic programming to solve the 0-1 Knapsack Problem.
• Returns a list of selected items that maximize the total value without exceeding the capacity.

Steps

• Create a 2D DP array: Stores intermediate results for subproblems.
• Fill the DP array:
  • Iterate through items and capacities.
  • For each cell, calculate the maximum value achievable considering the current item and remaining capacity.
• Reconstruct the solution: Backtrack through the DP array to find the selected items.

Take away points

• Bottom-up approach: Builds the solution from smaller subproblems to the final solution.
• Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
• Time complexity: O(nW), where n is the number of items and W is the capacity.
• Space complexity: O(nW), due to the DP array.