+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: 0 - 1 KnapSack problem (/thread-23858.html)
0 - 1 KnapSack problem - Stryker - Jan-20-2020
Hey folks, at the moment I am desperately trying to solve a problem with the well known KnapSack problem.
For those who don't know about it: The knapsack problem or rucksack problem is a problem in combinatorial optimization: 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. (Wikipedia)
I need to get a solution with recursive backtracking and the only thing I am allowed to edit is the function called "find_selection". The way how the algorithm has to work is also given:
Calculate weight and value of the current selection
If the maximal weight is exceeded:
Return an empty list.
Else:
Set/define the current selection as the best so far.
Repeat for every object included in the current selection:
Add the object to the current selection and the call the function recursively
If this search finds a better result than the best selection so far:
Save the returned selection as best so far.
Then remove the object from the current solution.
Return the best selection
I worked around this for quite a while now but couldn't get a proper solution. I am grateful for any help and piece of advice
The following is the code i wrote so far, like mentioned prior everything besides the "find_selection" must not be altered. The function needs to give me a list of the best solution.
When I run this code it prints the following:
Best solution: [0, 2, 3, 4, 5]
The total weight is: 400
The total value is: 380
which is nowhere near the optimum and even exceeds the maximum weight. It looks like the function just added the first five object, just leaving out [1] and i admittedly have no clue why this is the case.
wgt = [50, 50, 60, 80, 100, 110, 120, 150, 150, 200] #weight
val = [80, 80, 60, 50, 100, 90, 100, 170, 200, 240] #value
length = len(wgt)
max_wgt = 320
def calc_wgt(selection):
totalwgt = 0
for i in selection:
totalwgt = totalwgt + wgt[i]
return totalwgt
def calc_val(selection):
totalval = 0
for i in selection:
totalval = totalval + val[i]
return totalval
def miss_obj(selection):
found = []
for i in range(0, length):
found = found + [False]
for i in selection:
found[i] = True
numbers = []
for i in range(0, length):
if not found[i]:
numbers = numbers + [i]
return numbersat the moment I am desperat
def find_selection(curr_selection):
weight = calc_wgt(curr_selection) # Calculate weight and value of the current selection
value = calc_val(curr_selection) # #
if weight > max_wgt: # If the maximal weight is exceeded:
return [] # Return an empty list.
else: # Else:
best_selection = curr_selection # Set/define the current selection as the best so far.
missing = miss_obj(curr_selection) #
for i in missing: # Repeat for every object bot included in the current selection:
curr_selection.append(missing[i]) # Add the object to the current selection...
find_selection(curr_selection) # ...and call the function recursively.
if calc_val(curr_selection) > calc_val(best_selection): # If this search finds a better result than the best selection so far:
best_selection = curr_selection # Save the returned selection as best so far.
curr_selection.pop[-1] # Then remove the object from the current solution.
return best_selection # Return the best selection
result = find_selection([])
print("Best solution: " + str(result))
print("The total weight is: " + str(calc_wgt(result)))
print("The total value is: " + str(calc_val(result)))
RE: 0 - 1 KnapSack problem - Stryker - Jan-21-2020
I found some indentation errors I made and changed the code in line 43 and 44 and moved them one indentation to the left. The resulting Problem is that line 39 gives an "IndexError: List index out of range". Can anyone tell me why this is happening?