Dynamic Programming Algorithm

Given

•  0,1 Knapsack problem

Assuming

• We can divide the problem into optimal sub-structures 
• And there are overlapping solutions to the sub-structures

Problem

• We have n objects
• Each object has value, V
• Each object has weight, W
• We need to pick k items such that:
• We maximize the total value, TV, of k items picked
• But the total weight, TW, of the k items picked must be under a maximum weight limit of MW

Approach

• Since we have n items, we will need to evaluate value of all possible combinations of n items while maximizing value but still remaining under the maximum weight limit
• n items yield 2ⁿ combinations. Therefore, the complexity of this approach is O(2ⁿ)
  00000001
  00000010
  ...
  11111111
• Start a the tree with last item in the vector and move backwards in the vector
• Build a decision tree, depth-first, left-first where the left branch is the "don't take" branch
• When a node terminates (no more options), backtrack to the previous (upwards) nodes and complete the other branches

Example

∑_i=1ⁿ P_iX_i

where X_i is a vector of zeros and ones denoting whether an item is picked or not and P_i is the price or value of the item.

∑_i=1ⁿ W_iX_i <= C
where C is the maximum weight (constraint) and Wi is the weight of an item.

Additional constraints such as volume can be added to this algorithm.
∑_i=1ⁿ V_iX_i <= V_max
where V_max is the maximum volume (constraint) and Vi is the volume of an item.

Objective is the maximize the value!

Indices = [0, 1, 2]
Weights = [5, 3, 2]
Values = [9, 7, 8]

Constraint, MW = 5

The nodes represent a tuple of (index, capacity_remaining, cumulative_value)

Brute Force O(2ⁿ)

def solution_brute(w, v, i, aW)
$numCalls += 1
# puts 'called with index: ' + i.to_s + ' aW: ' + aW.to_s

if i == 0
if w[i] <= aW
return v[i]
else
return 0
end
end

without_i = solution_brute(w, v, i-1, aW)

if w[i] > aW 
return without_i
else
with_i = v[i] + solution_brute(w, v, i-1, aW - w[i])
end

[with_i, without_i].max
end

# Test
puts '----------------------------'
weights = [5, 3, 2]
values = [9, 7, 8]
startIndex = 2
aW = 5
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_brute weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

puts '----------------------------'
weights = [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2 ]
values = [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2 ]
startIndex = 15
aW = 21
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_brute weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

Result
----------------------------
Weights: [5, 3, 2]
Values: [9, 7, 8]
Optimal Value: 15
Total calls: 7
----------------------------
----------------------------
Weights: [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2]
Values: [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2]
Optimal Value: 49
Total calls: 21162
----------------------------

Optimized using Memoizatation O(n.s)

def solution_memo_helper(w, v, i, aW, m)
$numCalls += 1
# puts 'called with index: ' + i.to_s + ' aW: ' + aW.to_s

if m[[i, aW]] != nil
#puts 'found in memo'
return m[[i, aW]]
end

if i == 0
if w[i] <= aW
m[[i, aW]] = v[i]
return v[i]
else
m[[i, aW]] = 0
return 0
end
end

without_i = solution_memo_helper(w, v, i-1, aW, m)

if w[i] > aW 
m[[i, aW]] = without_i
return without_i
else
with_i = v[i] + solution_memo_helper(w, v, i-1, aW - w[i], m)
end

res = [with_i, without_i].max
m[[i, aW]] = res
res
end

def solution_memo(w, v, i, aW)
m = {}
return solution_memo_helper w, v, i, aW, m
end

# Test
puts '----------------------------'
weights = [5, 3, 2]
values = [9, 7, 8]
startIndex = 2
aW = 5
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_memo weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

puts '----------------------------'
weights = [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2 ]
values = [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2 ]
startIndex = 15
aW = 21
$numCalls  = 0;
puts 'Weights: ' +  weights.inspect
puts 'Values: ' +  values.inspect
puts 'Optimal Value: ' +  (solution_memo weights, values, startIndex, aW).inspect
puts 'Total calls: ' + $numCalls.to_s
puts '----------------------------'

Result
----------------------------
Weights: [5, 3, 2]
Values: [9, 7, 8]
Optimal Value: 15
Total calls: 7
----------------------------
----------------------------
Weights: [5, 3, 2, 4, 3, 6, 4, 2, 5, 3, 2, 4, 3, 6, 4, 2]
Values: [9, 7, 8, 6, 5, 4, 3, 2, 9, 7, 8, 6, 5, 4, 3, 2]
Optimal Value: 49
Total calls: 438
----------------------------

Comparison

Comparing the brute force verses memoized version of the algorithm, the following observations are made.

• Forthe second test case (16 items), with brute force 21,162 method calls were required to come up with an optimal solution
• For the second test case (16 items), with memoized approach only 438 method calls were required to come up with an optimal solution
• The efficiency gained with the memoized approach is at the expense of additional space required for memo entries. We have traded space for time.
• The complexity of the memoize approached is not strictly polynomial in the size of the input but rather in the size of the input, n, as well as the size of the solution, s. Such is the case because the eventual work done by the method is partly dependent on how many items are selected to come up with an optimal solution.