Implement 0/1 knapsack problem in python using backtracking

I would like to see how different sizes of input impact the backtracking algorithm for knapsack
I would like to find the maximum value possible.

  • random weight and value lists are generated using the generate function.
  • vsol[] has the final list of item indexes selected
  • temp[] holds the temporary selected indexes

output sited: 0 [] for every input selected item indexes

import random
import copy

weights = []
values = []
temp = []
vsol = []
isSol = False
solution = 0
def Knapsack(i,max,value):
    for k in range(i,len(values)):
        if max > 0:
            if weights[k] <= max:
                temp.append(k);
                if (value+values[k] >= solution):
                    solution = value+values[k];
                    isSol = True
            if (k+1)<n:
                Knapsack(k+1,max-weight[k],value+values[k])
            else:
                if isSol == True:
                    vsol = []
                    vsol = copy.deepcopy(temp)
                    temp = []
                    isSol = False
                else:
                    temp = []
                    return
        else:
            if isSol == True:
                vsol = []
                vsol = copy.deepcopy(temp)
                temp = []
                isSol = False
            else:
                temp = []
                return
    
    

def generator(n):
    l = [];
    for i in range(n):
        l.append(random.randint(1,100))
    return l    
def main():
    n = 10 #number of random numbers
    weights = generator(n);
    values = generator(n);
    Knapsack(0,10,0)
    print(solution,vsol)
    
main()

I tried deep copying the temp list to vsol list

Source: Python Questions

LEAVE A COMMENT