What is wrong with my implementation of the knapsack problem-CodePudding

items = [[profit, weight]...]

items = [[44,92], [46,4], [90,43], [72,83], [91,84], [40,68], [75,92], [35,82], [8,6], [54,44], [78,32], [40,18], [77,56], [15,83], [61,25], [17,96], [75,70], [29,48], [75,14], [63,58]]
max_weight = 269
def knapsack_bruteforce(items, max_weight):
    def backtrack(i, curr_profit, curr_weight):       
        if(i 1 >= len(items) or curr_weight   items[i 1][1] > max_weight):
            return curr_profit
            
        return max(backtrack(i 1, curr_profit   items[i 1][0], curr_weight   items[i 1][1]), backtrack(i 1, curr_profit, curr_weight))
        
    return backtrack(-1, 0, 0)

knapsack_bruteforce(items, max_weight) should return 550 as the maximum profit but I'm getting 528 instead.

CodePudding user response：

The problem is in the second part of the if condition:

if(i 1 >= len(items) or curr_weight   items[i 1][1] > max_weight):
    return curr_profit

When the second condition is true, you should still allow the second recursive call to be done -- the one where this weight is not included -- as there might still be a way to add another item (that has less weight). But as you return immediately here, that attempt is never made.

Without changing more than necessary to your code, you can fix this, by bailing out (returning a negative number) when the weight excess has already been made. So split your if into two:

if curr_weight > max_weight:
    return -1
if i 1 >= len(items):
    return curr_profit

CodePudding user response：

The problem is that you aren't exhaustively trying all the combinations; each time you remove an item, your recursive call needs to consider all the other items, not just the items after the one you removed.

Here's an example of a working brute-force solution; I added a functools.cache decorator (which requires immutable inputs, hence a tuple of tuples instead of a dict of lists) so I wouldn't have to wait all day for it to return the answer and make sure it works, but it should return the same answer without the memoization (just a lot more slowly). Memoization makes it go faster because otherwise you end up re-computing the exact same intermediate answers (arrived at in slightly different orders) quite a few times.

The thing to pay attention to is that in that max call we're iterating over all of items, and doing the recursive call with items[:i] items[i 1:], i.e. all the items except the i-th item.

from functools import cache

@cache
def knapsack(items: tuple[tuple[int, int], ...], max_weight: int) -> int:
    if all(weight > max_weight for _profit, weight in items):
        return 0  # can't add anything to the sack

    return max(
        profit   knapsack(items[:i]   items[i 1:], max_weight - weight)
        for i, (profit, weight) in enumerate(items)
        if weight <= max_weight
    )


print(knapsack((
    (44,92), (46,4), (90,43), (72,83), (91,84), (40,68), (75,92),
    (35,82), (8,6), (54,44), (78,32), (40,18), (77,56), (15,83),
    (61,25), (17,96), (75,70), (29,48), (75,14), (63,58)
), 269))  # 550