Knapsack - Brute Force

Problem definition

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Reference Knapsack Problem (wiki).

Data Structures

Input is a list of tuples, [(value, weight)], that represents items. From items list, all possible combinations are created. One possible combination is called an instance of the problem. Each raw instance is parsed into 3-tuple, where the first element is the sum of values, the second is the sum of weights and the third element is the raw list of items. [(value, weight)] -> (total_value, total_weight, [(value, weight)])

Combinations

Function subsequences enumerates all n-combinations of n objects. This is exactly what is needed for brute force algorithm in knapsack problem.

-- show Example of subsequences
import Data.List (subsequences)
combinations = subsequences [1,2,3]
-- /show
main = print combinations

Solution

Note: You can fiddle Main.hs, for example change n (problem size), capacity and seed variables and run code.

{-# START_FILE Knapsack.hs #-}
module Knapsack (knapsack) where

import Data.List (subsequences, filter, maximumBy)
import Data.Ord (comparing)

-- Brute Force Algorithm for Knapsack Problem
-- Complexity: O(2^n) (subsequences function)

-- show Brute Force Algorithm
-- Create a list of 3-tuples from item subsequences.
combos = map parse . subsequences

-- Filter feasible solutions based on instance's total weight. 
feasible w = filter ((>=) w . snd3)

-- Select maximum value from feasible set of combinations.
knapsack w = maximumBy (comparing fst3) . feasible w . combos

-- Create 3-tuple from each instance that contains total value and weight.
parse xs = (value, weight, xs) 
  where uz     = unzip xs
        value  = sum (fst uz) 
        weight = sum (snd uz)
-- /show

-- Getter functions for 3-tuple
fst3 (x,_,_) = x 
snd3 (_,y,_) = y

{-# START_FILE Main.hs #-}
import System.Random (Random, mkStdGen, randomRs)
import Knapsack

main = do
  -- show Solve example problem
  -- Input values
  let n = 10 -- problem size
  let capacity = 200 
  let seed = 42
  
  -- Get random values and weights
  let values = take n (random seed)
  let weights = take n (random (seed +1))
  
  let items = zip values weights
  let result = knapsack capacity items
  
  output items result
  -- /show
  
   
output items result = do 
  putStrLn $ "Items [(value, weight)] \n" ++ show items 
  putStrLn $ "\nResult (value, weight, [items])\n" ++ show result
  
-- For given seed, create infinite list of random integers from interval.
random seed = randomRs(1,100) (mkStdGen seed)
  
{-# START_FILE Knapsack.hs #-}
-- show
-- /show
module Knapsack (knapsack) where

import Data.List (subsequences, filter, maximumBy)
import Data.Ord (comparing)

-- Brute Force Algorithm for Knapsack Problem
-- Complexity: O(2^n) (subsequences function)

-- Create a list of 3-tuples from item subsequences.
combos = map parse . subsequences

-- Filter feasible solutions based on instance's total weight. 
feasible w = filter ((>=) w . snd3)

-- Select maximum value from feasible set of combinations.
knapsack w = maximumBy (comparing fst3) . feasible w . combos

-- Create 3-tuple from each instance that contains total value and weight.
parse xs = (value, weight, xs) 
  where uz     = unzip xs
        value  = sum (fst uz) 
        weight = sum (snd uz)

-- Getter functions for 3-tuple
fst3 (x,_,_) = x 
snd3 (_,y,_) = y

Complexity Analysis

O(2^n) (subsequences function)

• 2 outcomes: in or out
• ^n = Each outcome creates a new branch for the remaining elements in input items.

With n = 20 the above code will run just fine. When n is increased, execution time starts to increase rapidly. Compared to feasible size n = 20, how much more time and memory would be required?

• n = 21 -> 2^1 = 2
• n = 25 -> 2^5 = 32
• n = 30 -> 2^10 = 1024
• n = 100 -> 2^80 = 1.2e+24
• n = 1000 -> 2^980 = 1.0e+295