0-1 Knapsacks

You have    NNNitems, the  iii-th item having integer weight  wi∈Z≥0w_i \in \mathbb{Z}_{\geq 0}w​i​​∈Z​≥0​​and integer value  vi∈Z≥0v_i \in \mathbb{Z}_{\geq 0}v​i​​∈Z​≥0​​, and a bag with carrying capacity  BBB. 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  S⊆{1,2,...,N}S \subseteq \{1, 2, ..., N\}S⊆{1,2,...,N}such that  ∑i∈Svi\sum_{i \in S} v_i ∑​i∈S​​v​i​​is minimized but  ∑i∈Swi≤B\sum_{i \in S} w_i \leq B∑​i∈S​​w​i​​≤B.

This is known as the 0-1 Knapsack problem. Naïvely, by trying all the subsets, we can derive a  Θ(N⋅2N)\Theta(N \cdot 2^N)Θ(N⋅2​N​​)algorithm.

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

50.9s

Language:Julia

struct Item
  value ::Number
  weight::Number
end

function NaiveKnapsack(ItemList :: Vector{Item}, B :: Number)
  bestvalue  = 0
  bestsubset = Vector{Item}()
  for subset in combinations(ItemList)
    if sum([item.weight for item in subset]) <= B
      # Valid Subset of Items
      currvalue = sum([item.value for item in subset])
      if currvalue > bestvalue
        bestvalue  = currvalue
        bestsubset = subset
      end
    end
  end
  bestsubset
end

ItemList = [Item(3,2), Item(4,2), Item(5,3), Item(6,4)]
NaiveKnapsack(ItemList, 4)

2.4s

Language:Julia