Purva09/algorithm-battlefield

1"""Knapsack Problem Algorithms"""2 3 4def knapsack_dp(weights, values, capacity):5    """0/1 Knapsack using Dynamic Programming"""6    n = len(weights)7    dp = [[0] * (capacity + 1) for _ in range(n + 1)]8    9    for i in range(1, n + 1):10        for w in range(capacity + 1):11            if weights[i - 1] <= w:12                dp[i][w] = max(13                    values[i - 1] + dp[i - 1][w - weights[i - 1]],14                    dp[i - 1][w]15                )16            else:17                dp[i][w] = dp[i - 1][w]18    19    return dp[n][capacity]20 21 22def knapsack_backtracking(weights, values, capacity, index=0, current_weight=0, current_value=0):23    """0/1 Knapsack using Backtracking"""24    if index == len(weights):25        return current_value26    27    # Exclude current item28    exclude = knapsack_backtracking(weights, values, capacity, index + 1, current_weight, current_value)29    30    # Include current item if it fits31    include = 032    if current_weight + weights[index] <= capacity:33        include = knapsack_backtracking(34            weights, values, capacity, index + 1,35            current_weight + weights[index],36            current_value + values[index]37        )38    39    return max(include, exclude)40 41 42def knapsack_branch_bound(weights, values, capacity):43    """0/1 Knapsack using Branch and Bound"""44    n = len(weights)45    items = [(values[i] / weights[i], weights[i], values[i], i) for i in range(n)]46    items.sort(reverse=True)47    48    def bound(index, current_weight, current_value):49        if current_weight >= capacity:50            return current_value51        52        upper = current_value53        remaining = capacity - current_weight54        55        for i in range(index, n):56            if items[i][1] <= remaining:57                remaining -= items[i][1]58                upper += items[i][2]59            else:60                upper += (items[i][2] / items[i][1]) * remaining61                break62        63        return upper64    65    def solve(index, current_weight, current_value, best):66        if current_weight > capacity or index >= n:67            return best68        69        if bound(index, current_weight, current_value) <= best:70            return best71        72        include = solve(73            index + 1,74            current_weight + items[index][1],75            current_value + items[index][2],76            max(best, current_value)77        )78        79        exclude = solve(index + 1, current_weight, current_value, include)80        81        return max(include, exclude)82    83    return solve(0, 0, 0, 0)84