Python Forum
0 - 1 KnapSack problem
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
0 - 1 KnapSack problem
#1
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 Smile
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)))
Reply
#2
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?
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020