0-1 Knapsacks

1. Introduction

You haveitems, the -th item having integer weight and integer value , and a bag with carrying capacity . Your goal is to take items such that their value is maximized, but their weight cannot exceed the carrying capacity of the bag. In other words, find a subset of such that is minimized but .

This is known as the 0-1 Knapsack problem. Naïvely, by trying all the subsets, we can derive a algorithm.

using Pkg; 
Pkg.add("Combinatorics"); using Combinatorics;

0.9s

Julia

struct Item
  value ::Number
  weight::Number
end

Weight(ItemList :: Vector{Item}) = sum([item.weight for item in ItemList])
Value(ItemList :: Vector{Item}) = sum([item.value for item in ItemList])

function NaiveKnapsack(ItemList :: Vector{Item}, B)
  bestvalue  = 0
  for subset in combinations(ItemList)
    if Weight(subset) <= B
      # Valid Subset of Items
      currvalue = Value(subset)
      bestvalue = max(currvalue, bestvalue)
    end
  end
  bestvalue
end

ItemList = [Item(rand(1:100), rand(5:15)) for _ in 1:20]
B = 160
NaiveKnapsack(ItemList, B)

2.8s

Julia

This can be sped up by a factor of by considering a Gray code (or implementing it recursively). In light of the following algorithm, we shall not discuss this in greater detail.

2. Meet In The Middle

Algorithm 1 [Horowitz and Sahni 1974] The 0-1 Knapsack Problem can be solved in time.

Proof Let and. For each , it suffices to find such that is maximized subject to . This can be done efficiently by sorting the set , reducing the problem to a query on the maximum value of on a prefix of the sorted set.

0.6s

Julia

function HSKnapsack(ItemList :: Vector{Item}, B)
  N = length(ItemList)
  I = ItemList[1 : div(N, 2)]
  J = ItemList[div(N, 2) + 1 : N]
  
  QuerySet = [[Weight(Y), Value(Y)] for Y in combinations(J)]
  sort!(QuerySet)
  for i in 2:length(QuerySet)
    QuerySet[i][2] = max(QuerySet[i][2], QuerySet[i-1][2])
  end
  
  bestvalue = 0
  
  # Check for Empty X
  Idx = searchsortedlast(QuerySet, B; by = x -> x[1])
  if Idx != 0
    bestvalue = QuerySet[Idx][2]
  end
  
  for X in combinations(I)
    wt = Weight(X)
    wt > B && continue
    Idx = searchsortedlast(QuerySet, B - wt; by = x -> x[1])
    currvalue = Value(X)
    if Idx != 0 # Found our set Y
      currvalue += QuerySet[Idx][2]
    end
    bestvalue = max(bestvalue, currvalue)
  end
  bestvalue
end

HSKnapsack(ItemList, B)

0.6s

Julia

The above technique is also known as meet in the middle. Generally, we have a and wish to determine a subset with some property. We do this by partitioning into two sets and , taking time. For the technique to succeed, we hope to combine the partial results on and more efficiently than quadratic time (i.e. time), resulting in an algorithm in time. Often, this step is done via a combination of sorting and binary search.

Problem 2 Can we do better than time? Hint: Perform a different enumeration of the subsets of and .

Problem 3 Can we do better than time?

Problem 4 [Andrew Rayskiy] Given, a set of prime numbers, and , determine the number of distinct satisfying the property that every prime factor of is in .

Problem 5 [Dinur, Dunkelman, Keller and Shamir 2014] It is known that a 3 by 3 Rubik's Cube can be solved in 20 moves. Determine an algorithm to find a shortest sequence of moves to solve a scrambled cube.

3. NP-Completeness

A natural question to ask is does there exists a polynomial time algorithm for the 0-1 knapsack problem.

Theorem 6 [Karp 1972] Unless , there does not exist a polynomial time algoritm for 0-1 Knapsack.

Problem 7 Consider the Subset Sum problem: Given a set , is there a subset that sums to 0 (i.e. )? Give a polynomial time reduction from 3-Satisfiability to Subset Sum, then a polynomial time reduction from Subset Sum to 0-1 Knapsack. Hence or otherwise, show Theorem 5.

That’s disappointing. The 0-1 Knapsack problem is unlikely to admit a polynomial time solution. For -complete problems, we should look towards special cases where it is possible to solve the problem quickly. Fortunately, we have the following algorithm when is small.

4. Dynamic Programming

Algorithm 8 The 0-1 Knapsack problem can be solved in time.

Proof Define as the solution to the 0-1 Knapsack problem on the first items and a bag of carrying capacity . Observe that

it suffices to compute ,
for all values of , , and

f(k, C) = \max(f(k-1, C), f(k-1, C - w_k) + v_k).

function f(ItemList :: Vector{Item}, Memoize :: Array{Int, 2}, k, C)
  (k == 0 || C == 0) && return 0
  Memoize[k, C] != -1 && return Memoize[k, C]
  
  ans = f(ItemList, Memoize, k-1, C)
  if C >= ItemList[k].weight
    ans = max(ans, 
      f(ItemList, Memoize, k-1, C - ItemList[k].weight)+ ItemList[k].value)
  end
  
  Memoize[k, C] = ans
end

function DPKnapsack(ItemList :: Vector{Item}, B) 
  Memoize = -ones(Int, length(ItemList), B)
  f(ItemList, Memoize, length(ItemList), B)
end

DPKnapsack(ItemList, B)

0.4s

Julia

This is not the only special case with an efficient algorithm. For example, if and for all , there is a linear time greedy solution. Another instance we can improve on Algorithm 8 is when we have only a small number of distinct weights, say . Here, there is a algorithm. The following problems give a few more variants.

Problem 9 Let . Show that the 0-1 Knapsack problem can also be solved in time.

Problem 10 [Evgeny Zamyatin] Given a multiset of positive integers with sum , determine efficiently if you can partition into two disjoint subsets such that they have equal sum (i.e. ).

Problem 11 [Gennady Korotkevich] Given a multiset of positive integers with the -th element , determine efficiently the median of the multiset .

Problem 12 Determine other special cases of where we can have an improvement over Algorithms 1 and 8.