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.
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)))