Knapsack Problem

Definition

Definition

The knapsack (rucksack) problem is about optimizing the selection of items with weights and values to fit within a given limit while maximizing total value. It's named after the challenge of filling a fixed-size knapsack with valuable items. For instance, one version involves choosing boxes to maximize earnings while staying within a weight limit, such as 15 kg. Problem of maximizing the value of items in a knapsack without exceeding its capacity, with items being either selected or not.

0/1 Knapsack Problem

Each item can only be selected once. It involves a set of items with weights wi and values vi, along with a maximum weight capacity W, maximize $\displaystyle\sum_{i = 1}^n v_i x_i$ subject to $\displaystyle\sum_{i = 1}^n w_i x_i \leq W$ and $x_i \in \{0, 1\}$ where $x_i$ signifies the quantity of item i to add to the knapsack. The objective is to maximize the total value of the items while ensuring their combined weight doesn't exceed the knapsack's capacity

Bounded knapsack problem (BKP)

Removes the restriction that there is only one of each item, but restricts the number $x_i$ of copies of each kind of item to a maximum non-negative integer value c: maximize $\displaystyle\sum_{i = 1}^n v_i x_i$ subject to $\displaystyle\sum_{i = 1}^n w_i x_i \leq W$ and $0 \leq x_i \leq c$

Unbounded knapsack problem (UKP)

Places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on $x_i$ is that it is a non-negative integer, maximize $\displaystyle\sum_{i = 1}^n v_i x_i$ subject to $\displaystyle\sum_{i = 1}^n w_i x_i \leq W$ and $x_i \geq 0$

Explanation

Visualize a grid where each cell represents a combination of items and their capacity. Initially filled with zeros, the grid is primed for calculations. We systematically explore each item and capacity option, toggling between inclusion and exclusion of items to optimize value. By updating the grid iteratively, the bottom-right cell reveals the maximum achievable value given the constraints

Guidance

• Begin by setting up a grid, like a table, with rows for each item and columns for each possible capacity, starting from zero and going up to the maximum capacity
• Go through each item one by one
  • for each item, consider every capacity from zero up to the maximum capacity
    • if the weight of the current item can fit into the current capacity
      • calculate the value if we include the item: take the maximum between the value obtained by including the item and the value obtained by excluding it
    • if the weight of the item is too much for the current capacity, just keep the value same as the previous item
• The maximum value achievable is the number in the bottom-right corner of the table/grid

Tips

• optimize the space complexity by using a 1D array instead of a 2D array if possible
• ensure that the items are sorted either by weight or by value to optimize the algorithm
• handle edge cases such as when the capacity is zero or when there are no items

Practice

Practice

knapsack(weights[], values[], capacity):
    n = length(weights)
    dp = array of size (n + 1) x (capacity + 1) filled with zeros

    for i from 1 to n:
        for j from 1 to capacity:
            if weights[i] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i]] + values[i])
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][capacity]

Solution

package main

// 0/1 Knapsack Problem
func knapsack01(weights []int, values []int, capacity int) int {
	n := len(weights)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}

	for i := 1; i <= n; i++ {
		for j := 0; j <= capacity; j++ {
			if weights[i-1] > j {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
			}
		}
	}

	return dp[n][capacity]
}

// Unbounded Knapsack Problem
func unboundedKnapsack(weights []int, values []int, capacity int) int {
	dp := make([]int, capacity+1)

	for i := 0; i <= capacity; i++ {
		for j := 0; j < len(weights); j++ {
			if weights[j] <= i {
				dp[i] = max(dp[i], dp[i-weights[j]]+values[j])
			}
		}
	}

	return dp[capacity]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

import java.util.Arrays;

public class Knapsack {

  // 0/1 Knapsack Problem
  public static int knapsack01(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= capacity; j++) {
        if (weights[i - 1] > j) {
          dp[i][j] = dp[i - 1][j];
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
        }
      }
    }

    return dp[n][capacity];
  }

  // Unbounded Knapsack Problem
  public static int unboundedKnapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];

    for (int i = 0; i <= capacity; i++) {
      for (int j = 0; j < weights.length; j++) {
        if (weights[j] <= i) {
          dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
        }
      }
    }

    return dp[capacity];
  }
}

// 0/1 Knapsack Problem
function knapsack01(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const weight = weights[i - 1];
    const value = values[i - 1];
    for (let j = 0; j <= capacity; j++) {
      if (weight > j) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value);
      }
    }
  }

  return dp[n][capacity];
}

// Unbounded Knapsack Problem
function unboundedKnapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(capacity + 1).fill(0);

  for (let i = 0; i <= capacity; i++) {
    for (let j = 0; j < n; j++) {
      if (weights[j] <= i) {
        dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
      }
    }
  }

  return dp[capacity];
}

import kotlin.math.max

// 0/1 Knapsack Problem
fun knapsack01(weights: IntArray, values: IntArray, capacity: Int): Int {
    val n = weights.size
    val dp = Array(n + 1) { IntArray(capacity + 1) }

    for (i in 1..n) {
        for (j in 0..capacity) {
            dp[i][j] = if (weights[i - 1] > j) {
                dp[i - 1][j]
            } else {
                max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
            }
        }
    }

    return dp[n][capacity]
}

// Unbounded Knapsack Problem
fun unboundedKnapsack(weights: IntArray, values: IntArray, capacity: Int): Int {
    val dp = IntArray(capacity + 1)

    for (i in 0..capacity) {
        for (j in weights.indices) {
            if (weights[j] <= i) {
                dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
            }
        }
    }

    return dp[capacity]
}

# 0/1 Knapsack Problem
def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][capacity]

# Unbounded Knapsack Problem
def unbounded_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(capacity + 1):
        for j in range(len(weights)):
            if weights[j] <= i:
                dp[i] = max(dp[i], dp[i - weights[j]] + values[j])

    return dp[capacity]

// 0/1 Knapsack Problem
fn knapsack_01(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let n = weights.len();
    let mut dp = vec![vec![0; capacity + 1]; n + 1];

    for i in 1..=n {
        for j in 0..=capacity {
            if weights[i - 1] <= j {
                dp[i][j] = dp[i - 1][j].max(dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    dp[n][capacity]
}

// Unbounded Knapsack Problem
fn unbounded_knapsack(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let mut dp = vec![0; capacity + 1];

    for i in 0..=capacity {
        for j in 0..weights.len() {
            if weights[j] <= i {
                dp[i] = dp[i].max(dp[i - weights[j]] + values[j]);
            }
        }
    }

    dp[capacity]
}

// 0/1 Knapsack Problem
function knapsack01(
  weights: number[],
  values: number[],
  capacity: number,
): number {
  const n = weights.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () =>
    Array(capacity + 1).fill(0),
  );

  for (let i = 1; i <= n; i++) {
    const weight = weights[i - 1];
    const value = values[i - 1];
    for (let j = 0; j <= capacity; j++) {
      if (weight > j) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value);
      }
    }
  }

  return dp[n][capacity];
}

// Unbounded Knapsack Problem
function unboundedKnapsack(
  weights: number[],
  values: number[],
  capacity: number,
): number {
  const n = weights.length;
  const dp: number[] = Array(capacity + 1).fill(0);

  for (let i = 0; i <= capacity; i++) {
    for (let j = 0; j < n; j++) {
      if (weights[j] <= i) {
        dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
      }
    }
  }

  return dp[capacity];
}