import gurobipy as gp
from gurobipy import GRB

def solve_knapsack(weights, values, capacity):
    # Number of items
    n = len(weights)

    # Create a new model
    model = gp.Model("knapsack")

    # Create variables
    x = model.addVars(n, vtype=GRB.BINARY, name="x")

    # Set objective: maximize total value
    model.setObjective(gp.quicksum(values[i] * x[i] for i in range(n)), GRB.MAXIMIZE)

    # Add constraint: total weight must be less than or equal to capacity
    model.addConstr(gp.quicksum(weights[i] * x[i] for i in range(n)) <= capacity, "capacity")

    # Optimize the model
    model.optimize()

    # Print the results
    if model.status == GRB.OPTIMAL:
        print("Optimal solution found")
        selected_items = [i for i in range(n) if x[i].x > 0.5]
        print(f"Selected items: {selected_items}")
        print(f"Total value: {model.objVal}")
    else:
        print("No optimal solution found")

if __name__ == "__main__":
    # Example data
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 8]
    capacity = 5

    solve_knapsack(weights, values, capacity)