knapsack problem using brute force method in python

Question

I am applying the following code to obtain the max CBU. Can I also get the list of selected items in a knapsack? Here is my code

def knapsack(CBU, weight, Capacity):
    return knapsacksolution(CBU, weight, Capacity, 0)
def knapsacksolution(CBU, weight, Capacity, currentIndex):
    
    if Capacity <= 0 or currentIndex >= len(CBU):
        return 0
    CBU1 = 0
    #selecting a box at currentindex
    if CBU[currentIndex] <= Capacity:
         CBU1 = CBU[currentIndex] + knapsacksolution(CBU, weight, Capacity - CBU[currentIndex], currentIndex+1)
    #excluding a box at currentindex
    CBU2 = knapsacksolution(CBU, weight, Capacity, currentIndex+1)
    
    return max(CBU1, CBU2)
def main():
    weight = [20,15,17,24]
    CBU = [3,2,3,4]
    Capacity = 8
    
    OptimalCBU = knapsack(CBU, weight, Capacity)
    print('Optimal CBU for CBU:{} with weight:{} for Capacity:{} is:{}'.format(CBU, weight, Capacity, OptimalCBU))
if __name__ == '__main__':
    main()

Result is as follow Optimal CBU for CBU:[3, 2, 3, 4] with weight:[20, 15, 17, 24] for Capacity:8 is:8

Answer 1

Just recently I learned the itertools.combinations method (from reading solutions on SO). It seems like a simple tool for generating all of the various configurations of the knapsack.

In the code below, we use combinations to find all of the combinations of the knapsack configuration, throwing out all of the combos that are over the capacity.

Having used brute force to find all of the viable answers, it remains simply to sort the results and present the maximum pay solution.

Here's the code that does just this (it has not been optimized):

import itertools

def sum_solution( solutions ):
  pay, load = 0,0
  for block in solutions:
    pay += block[0]
    load += block[1]

  return pay, load 

def knapsack( capacity, blocks ):

  solutions = []
  for count in range(len(blocks)+1):
    for solution in itertools.combinations( blocks, count ):
      pay,load = sum_solution( solution ) 
      if load <= capacity:
        solutions.append((pay,load,solution))

  solutions.sort( reverse = True, key = lambda x : x[0] )
  return solutions


solutions = knapsack( 15, [ (4,12) , (2,1) , (10,4), (1,1), (2,2) ])
solution = solutions[0]
print( f"Maximum Cash:  {solution[0]}  Weight: {solution[1]} Contents:  {solution[2]}")


print(f"Cash  Weight Contents")
for solution in solutions:
  print(f"{solution[0]:5d} {solution[1]:6d} {solution[2]}")

Here's the results:

Maximum Cash:  15  Weight: 8 Contents:  ((2, 1), (10, 4), (1, 1), (2, 2))
Cash  Weight Contents
   15      8 ((2, 1), (10, 4), (1, 1), (2, 2))
   14      7 ((2, 1), (10, 4), (2, 2))
   13      6 ((2, 1), (10, 4), (1, 1))
   13      7 ((10, 4), (1, 1), (2, 2))
   12      5 ((2, 1), (10, 4))
   12      6 ((10, 4), (2, 2))
   11      5 ((10, 4), (1, 1))
   10      4 ((10, 4),)
    8     15 ((4, 12), (2, 1), (2, 2))
    7     14 ((4, 12), (2, 1), (1, 1))
    7     15 ((4, 12), (1, 1), (2, 2))
    6     13 ((4, 12), (2, 1))
    6     14 ((4, 12), (2, 2))
    5     13 ((4, 12), (1, 1))
    5      4 ((2, 1), (1, 1), (2, 2))
    4     12 ((4, 12),)
    4      3 ((2, 1), (2, 2))
    3      2 ((2, 1), (1, 1))
    3      3 ((1, 1), (2, 2))
    2      1 ((2, 1),)
    2      2 ((2, 2),)
    1      1 ((1, 1),)
    0      0 ()

I modified the problem statement to use an example I found at wikipedia. Simply put, the blocks were:

$4, 12 kg
$2, 2 kg
$1, 1 kg
$2, 1 kg
$10,4 kg 

You can see that I coded the blocks as this:

[ (4,12) , (2,1) , (10,4), (1,1), (2,2) ]

Anyway, HTH.