CODEWITHSUNDEEP
pythonbrute-forceknapsack-problem
Astrus
Astrus

Reputation: 193

Resolution of the knapsack approach by bruteforce in python

I'm actually trying to resolve the knapsack problem with bruteforce. I know it's not efficient at all, I just want to implement it in python.

The problem is it take long time. In my point of view too much time for a bruteforce. So maybe I make some mistakes in my code...

def solve_it(input_data):
# Start the counting clock
start_time = time.time()

# Parse the input
lines = input_data.split('\n')
firstLine = lines[0].split()
item_count = int(firstLine[0])
capacity = int(firstLine[1])

items = []

for i in range(1, item_count+1):
    line = lines[i]
    parts = line.split()
    items.append(Item(i-1, int(parts[0]), int(parts[1])))

# a trivial greedy algorithm for filling the knapsack
# it takes items in-order until the knapsack is full
value = 0
weight = 0
best_value = 0

my_list_combinations = list()
our_range = 2 ** (item_count)

print(our_range)

output = ""

for i in range(our_range):
    # for exemple if item_count is 7 then 2 in binary is
    # 0000010
    binary = binary_repr(i, width=item_count)

    # print the value every 0.25%
    if (i % (our_range/400) == 0):
        print("i : " + str(i) + '/' + str(our_range) + ' ' +
            str((i * 100.0) / our_range) + '%')
        elapsed_time_secs = time.time() - start_time
        print "Execution: %s secs" % \
            timedelta(seconds=round(elapsed_time_secs))

    my_list_combinations = (tuple(binary))

    sum_weight = 0
    sum_value = 0

    for item in items:
        sum_weight += int(my_list_combinations[item.index]) * \
            int(item.weight)

    if sum_weight <= capacity:
        for item in items:
            sum_value += int(my_list_combinations[item.index]) * \
                int(item.value)

        if sum_value > best_value:
            best_value = sum_value
            output = 'The decision variable is : ' + \
                str(my_list_combinations) + \
                ' with a total value of : ' + str(sum_value) + \
                ' for a weight of : ' + str(sum_weight) + '\n'
return output

Here is the file containing the 30 objects :

30 100000 # 30 objects with a maximum weight of 100000
90000 90001
89750 89751
10001 10002
89500 89501
10252 10254
89250 89251
10503 10506
89000 89001
10754 10758
88750 88751
11005 11010
88500 88501
11256 11262
88250 88251
11507 11514
88000 88001
11758 11766
87750 87751
12009 12018
87500 87501
12260 12270
87250 87251
12511 12522
87000 87001
12762 12774
86750 86751
13013 13026
86500 86501
13264 13278
86250 86251

I dont show the code relative to the reading of the file because I think it's pointless... For 19 objects I'm able to solve the problem with bruteforce in 14 seconds. But for 30 objects I have calculated that it would take me roughly 15h. So I think that there is a problem in my computing...

Any help would be appreciated :)

Astrus

Upvotes: 0

Views: 2178

Answers (1)

wildwilhelm
wildwilhelm

Reputation: 5019

Your issue, that solving the knapsack problem takes too long, is indeed frustrating, and it pops up in other places where algorithms are high-order polynomial or non-polynomial. You're seeing what it means for an algorithm to have exponential runtime ;) In other words, whether your python code is efficient or not, you can very easily construct a version of the knapsack problem that your computer won't be able to solve within your lifetime.

Exponential running time means that every time you add another object to your list, the brute-force solution will take twice as long. If you can solve for 19 objects in 14 seconds, that suggests that 30 objects will take 14 secs x (2**11) = 28672 secs = about 8 hours. To do 31 objects might take about 16 hours. Etc.

There are dynamic programming approaches to the knapsack problem which trade off runtime for memory (see the Wikipedia page), and there are numerical optimisers which are tuned to solve constraint-based problems very quickly (again, Wikipedia), but none of this really alters the fact that finding exact solutions to the knapsack problem is just plain hard.

TL;DR: You're able to solve for 19 objects in a reasonable amount of time, but not for 30 (or 100 objects). This is a property of the problem you're solving, and not a shortcoming with your Python code.

Upvotes: 1

Related Questions