knapsack.py

from setup_problem import load_parameters
from metrics import get_metrics
import heapq

################## Recursive ##################


def knapsack_rec(parameters):
    capacity = parameters["capacity"]
    items = parameters["items"]
    n_left = len(items)
    nb_visits = 0

    def solve(cap, nb_left):
        nonlocal nb_visits
        nb_visits += 1

        if nb_left == 0 or cap == 0:  # No capacity left or no items left
            return 0, cap

        # Checking last non checked item
        current_item = items[nb_left - 1]
        weight = current_item["weight"]

        taken = 0
        # take item if it fits, and continue recursion from this choice
        if weight <= cap:
            profits, cap_left = solve(cap - weight, nb_left - 1)
            taken = current_item["profit"] + profits

        # don't take the item and continue recursion from this choice
        not_taken, cap_left = solve(cap, nb_left - 1)

        return max(taken, not_taken), cap_left

    result, capacity_left = solve(capacity, n_left)

    return result, capacity_left, {"nb_visits": nb_visits}

################## Dynamic Programming ##################


def knapsack_rec_td(parameters):
    capacity = parameters["capacity"]
    items = parameters["items"]
    n_items = len(items)
    nb_visits = 0

    # Memoization table: Rows = items, Cols = capacity
    # Initialized with None to differentiate from a 0 profit result
    memo = [[None for _ in range(capacity + 1)] for _ in range(n_items + 1)]

    def solve(cap, nb_left):
        nonlocal nb_visits
        nb_visits += 1

        if nb_left == 0 or cap == 0:
            return 0, cap

        # Checking memorisation table and return cached result
        if memo[nb_left][cap] is not None:
            return memo[nb_left][cap]

        current_item = items[nb_left - 1]
        weight = current_item["weight"]

        taken_profit = 0
        cap_taken = cap
        if weight <= cap:
            p, c = solve(cap - weight, nb_left - 1)
            taken_profit = current_item["profit"] + p
            cap_taken = c

        not_taken_profit, cap_not_taken = solve(cap, nb_left - 1)

        # decision and caching
        if taken_profit >= not_taken_profit:
            res = (taken_profit, cap_taken)
        else:
            res = (not_taken_profit, cap_not_taken)

        memo[nb_left][cap] = res
        return res

    result, capacity_left = solve(capacity, n_items)
    return result, capacity_left, {"nb_visits": nb_visits}


def knapsack_bu(parameters):
    """
    Switching to iterative by designing a bottom-up solver that uses a table to store maximums
    such that maximums[i][j] stores the maximum value we can get using i items such that the knapsack capacity is j
    """
    capacity = parameters["capacity"]
    items = parameters["items"]
    n = len(items)

    nb_visits = 0  # Total cells filled in the DP table

    maximums = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]  # Initialization

    # Build table in bottom-up manner
    for i in range(1, n + 1):
        current_item = items[i - 1]
        weight = current_item["weight"]

        for j in range(1, capacity + 1):
            nb_visits += 1

            # If item fits in current capacity
            if weight <= j:
                # Max between taking and not taking the item
                maximums[i][j] = max(current_item["profit"] + maximums[i - 1][j - weight],
                                     maximums[i - 1][j])
            else:
                # Item doesn't fit
                maximums[i][j] = maximums[i - 1][j]

    best_profit = maximums[n][capacity]

    # Backtracking through table to find capacity left
    temp_w = capacity
    temp_p = best_profit
    for i in range(n, 0, -1):
        if temp_p <= 0:
            break
        # If result came from taking the item
        if temp_p != maximums[i - 1][temp_w]:
            temp_w -= items[i - 1]["weight"]
            temp_p -= items[i - 1]["profit"]

    capacity_left = temp_w

    return best_profit, capacity_left, {"nb_visits": nb_visits}


def knapsack_bu_opt(parameters):
    capacity = parameters["capacity"]
    items = parameters["items"]
    n = len(items)
    nb_visits = 0

    # 1D space-optimized table
    maximums = [0] * (capacity + 1)

    # Tracking the number of inner-loop updates to get capacity_left.
    for i in range(n):
        weight = items[i]["weight"]
        profit = items[i]["profit"]

        # Iterating backwards to ensure each item is used only once
        for j in range(capacity, weight - 1, -1):
            nb_visits += 1
            if maximums[j - weight] + profit > maximums[j]:
                maximums[j] = maximums[j - weight] + profit

    best_profit = maximums[capacity]

    # Finding capacity_left requires either a 2D bitmask or re-running the logic
    # For now I'll return -1 and try to add it later,
    # else it will simply be a limit for this implementation
    capacity_left = -1

    return best_profit, capacity_left, {"nb_visits": nb_visits}

################## Branch and bound ##################


class Node:
    def __init__(self, level, profit, weight, bound=0):
        self.level = level  # Item index in the sorted list
        self.profit = profit  # Total profit accumulated
        self.weight = weight  # Total weight accumulated
        self.bound = bound  # Theoretical maximum profit this branch can achieve

    # Using a max-priority queue, we need the node with the highest bound first
    def __lt__(self, other):
        return self.bound > other.bound


def get_bound(node, n, capacity, items):
    """Calculates best possible profit using fractional logic."""
    if node.weight >= capacity:
        return 0

    profit_bound = node.profit
    j = node.level + 1
    total_weight = node.weight

    # Fill with whole items
    while j < n and total_weight + items[j]['weight'] <= capacity:
        total_weight += items[j]['weight']
        profit_bound += items[j]['profit']
        j += 1

    # Fill remaining capacity with fraction of the next item
    if j < n:
        profit_bound += (capacity - total_weight) * (items[j]['profit'] / items[j]['weight'])

    return profit_bound


def knapsack_bnb(parameters):
    raw_items = parameters["items"]
    capacity = parameters["capacity"]
    n = len(raw_items)
    nb_visits = 0

    # Sorting items by profit/weight ratio
    items = sorted(raw_items, key=lambda x: x['profit'] / x['weight'], reverse=True)
    queue = []

    # Root node
    root = Node(-1, 0, 0)
    root.bound = get_bound(root, n, capacity, items)
    heapq.heappush(queue, root)

    max_profit = 0
    final_weight = 0  # Track capacity left

    while queue:
        # Explore node with best bound
        curr = heapq.heappop(queue)
        nb_visits += 1

        # Pruning: if bound is worse than current best, skip branch
        if curr.bound <= max_profit:
            continue

        next_level = curr.level + 1  # Next item
        if next_level == n:
            continue

        # take next item
        item = items[next_level]
        if curr.weight + item['weight'] <= capacity:
            taken_node = Node(next_level,
                              curr.profit + item['profit'],
                              curr.weight + item['weight'])

            if taken_node.profit > max_profit:
                max_profit = taken_node.profit
                final_weight = taken_node.weight

            taken_node.bound = get_bound(taken_node, n, capacity, items)
            if taken_node.bound > max_profit:
                heapq.heappush(queue, taken_node)

        # don't take next item
        not_taken_node = Node(next_level, curr.profit, curr.weight)
        not_taken_node.bound = get_bound(not_taken_node, n, capacity, items)

        if not_taken_node.bound > max_profit:
            heapq.heappush(queue, not_taken_node)

    capacity_left = capacity - final_weight
    return max_profit, capacity_left, {"nb_visits": nb_visits}


def knapsack(json_file, mode):
    parameters = load_parameters(json_file)

    if mode == "recursive":
        return get_metrics(knapsack_rec, parameters)
    elif mode == "recursive_td":
        return get_metrics(knapsack_rec_td, parameters)
    elif mode == "iterative_bu":
        return get_metrics(knapsack_bu, parameters)
    elif mode == "iterative_bu_opt":
        return get_metrics(knapsack_bu_opt, parameters)
    elif mode == "bnb":
        return get_metrics(knapsack_bnb, parameters)