Knapsack 0-1 solver

binary_knapsack_solver.py

# -----------------------------------------------------------------------------
# Binary Knapsack Solver v0.1.0
# -----------------------------------------------------------------------------
# Copyright (c) 2025 Stefano Raneri
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
# -----------------------------------------------------------------------------


def solve(
    profits_vec: list[int], weights_vec: list[int], n_objects: int, total_cap: int
) -> tuple[int, list[bool]] | None:
    """Solves knapsack 0-1

    Returns a two elements tuple, with the first element being the optimal value,
    the second element is the optimal (binary) solution.
    Returns None in case of errors...
    """

    matrix = __compute_optimal_value(profits_vec, weights_vec, n_objects, total_cap)
    zstar = matrix[total_cap][n_objects]
    xstar = __extract_solution(matrix, weights_vec, n_objects, total_cap)
    return zstar, xstar


def __ask_number(prompt: str) -> int | None:
    """Asks an integer number repeatedly"""
    while True:
        try:
            return int(input(prompt).strip())
        except ValueError:
            continue
        except KeyboardInterrupt:
            return None


def __ask_num_vector(n: int) -> list[int] | None:
    """Asks integer values for each i-th object, having `n` total objects"""
    vec = []
    for i in range(n):
        p = __ask_number(f"\nInsert value for the object x{i+1}\n>>")
        if p is None:
            return None
        if p < 0:
            print("\nProfit value must be >= 0")
            return None
        vec.append(p)
    return vec


def __compute_optimal_value(
    profits_vec: list[int], weights_vec: list[int], n_objects: int, total_cap: int
) -> list[list[int]]:
    """Restituisce la tabella DP riempita per il valore ottimo"""
    matrix = [[0] * (n_objects + 1) for _ in range(total_cap + 1)]

    for k in range(1, total_cap + 1):
        for i in range(1, n_objects + 1):
            p = profits_vec[i - 1]
            w = weights_vec[i - 1]
            if k >= w:
                matrix[k][i] = max(matrix[k][i - 1], p + matrix[k - w][i - 1])
            else:
                matrix[k][i] = matrix[k][i - 1]

    return matrix


def __extract_solution(
    matrix: list[list[int]], weights_vec: list[int], n_objects: int, total_cap: int
) -> list[bool]:
    """Dato il DP matrix, estrae la soluzione binaria ottima"""
    xstar = [False] * n_objects
    k = total_cap
    for i in range(n_objects, 0, -1):
        if matrix[k][i] != matrix[k][i - 1]:
            xstar[i - 1] = True
            k -= weights_vec[i - 1]
    return xstar


def __main(
    profits_vec: list[int] = None,
    weights_vec: list[int] = None,
    n_objects: int = None,
    total_cap: int = None,
):
    """Main entry point"""

    if n_objects is None:
        n_objects = __ask_number("\nHow many objects?\n>>")
        if n_objects is None or n_objects <= 0:
            print("\nMust be > 0")
            return -1

    if total_cap is None:
        total_cap = __ask_number("\nTotal capacity of the sack?\n>>")
        if total_cap is None or total_cap < 0:
            print("\nMust be >= 0")
            return -1

    if profits_vec is None:
        print("\nPlease insert the profit values for each i-th object...")
        profits_vec = __ask_num_vector(n_objects)

    if weights_vec is None:
        print("\nPlease insert the weights values for each i-th object...")
        weights_vec = __ask_num_vector(n_objects)

    zstar, xstar = solve(profits_vec, weights_vec, n_objects, total_cap)

    print(
        "\nz = " + " + ".join((f"{p}(x{i+1})" for i, p in enumerate(profits_vec))),
        end="\n\n",
    )
    print(
        " + ".join((f"{w}(x{i+1})" for i, w in enumerate(weights_vec)))
        + f" <= {total_cap}"
    )
    print("\nxi ∈ {0,1} i = {" + " ".join(str(i + 1) for i in range(n_objects)) + "}")

    print("\nSolution is  x* = |" + " ".join("1" if b else "0" for b in xstar) + "|")
    print(f"\nOptimal is  z* = {zstar}")

    return 0


if __name__ == "__main__":
    from sys import exit as sys_exit

    sys_exit(__main())