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.