I'm solving a knapsack similar problem: which is to print out the first combination of objects that has value above a number but weight below a limit.
I have tried:
value = [10, 8, 7, 6, 4]
weight = [8, 4, 3, 3, 1]
name = ['A','B','C','D','E']
Wlimit = 8
Vlimit = 8
def ID(maxDepth):
for i in range(1, maxDepth):
knapsack = []
if (DFS(knapsack, 0, 0, i)):
return True
else:
print("cannot find solution")
return False
def DFS(knapsack, currentValue, currentWeight, maxDepth):
# If reached the maximum depth, stop recursing.
if maxDepth <= 0 : return False
if currentValue >= Vlimit and currentWeight <= Wlimit:
print(knapsack)
return True
for i in range(len(name)):
if name[i] not in knapsack:
if ((currentWeight + weight[i]) < Wlimit):
knapsack.append(name[i])
DFS(knapsack, currentValue + value[i], currentWeight + weight[i], maxDepth - 1)
knapsack = knapsack[:-1]
DFS(knapsack, currentValue, currentWeight, maxDepth - 1)
else:
DFS(knapsack, currentValue, currentWeight, maxDepth - 1)
return False
I know the tree looks like this
But I don't know how to fix the code with the correct logic Hope someone can give me a hand on it.
Thank you!!
I tried this and it works for some samples:
weight = [1,1,3,4,5]
value = [2,1,5,3,5]
name = ['A','B','C','D','E']
knapsack = []
limit_weight = 8
limit_value = 8
n = 5 # number of items
def ID(maxDepth):
for i in range(maxDepth):
found, val, arr = DFS(i)
if found:
return arr
return False
def DFS(maxDepth, idx = 0, sum_val = 0, sum_weight = 0, arr = []):
if maxDepth < 0 : return False, None, None
if sum_weight > limit_weight : return False, None, None # elements weights exceed knapsack limit
if sum_val > limit_value : return True, sum_val, arr # elements values greater than required
if idx >= n : return False, None, None # no more elements and no solution (otherwise we would have returned from the previous line)
for i in range(idx,n):
n_arr = arr.copy()
n_arr.append(name[i])
found, new_sum_val, new_sum_weight = DFS(maxDepth-1, i+1, sum_val + value[i], sum_weight + weight[i], n_arr)
if found : return found, new_sum_val, new_sum_weight
return False, None, None # didn't find a solution
res = ID(4)
print(res)
The code returns False if no solution is found, and a list of element names if a solution is found. please let me know if you find anything unclear.