Ad-Ass6-BranchnBound

import numpy as np

def club_assignment_bnb(cost_matrix):
    n = len(cost_matrix)
    if n == 0 or len(cost_matrix[0]) != n:
        raise ValueError("Invalid cost matrix")

    def bound(node, level):
        bound_val = 0
        assigned_students = set()
        assigned_clubs = set()

        for i in range(level):
            assigned_students.add(node[i][0])
            assigned_clubs.add(node[i][1])
            bound_val += cost_matrix[node[i][0]][node[i][1]]

        for i in range(level, n):
            min_cost = float('inf')
            for j in range(n):
                if j not in assigned_clubs:
                    min_cost = min(min_cost, cost_matrix[i][j])
            bound_val += min_cost

        return bound_val

    def branch_and_bound(node, level, min_cost, min_assignment):
        nonlocal best_cost, best_assignment
        if level == n:
            current_cost = sum(cost_matrix[node[i][0]][node[i][1]] for i in range(n))
            if current_cost < best_cost:
                best_cost = current_cost
                best_assignment = node.copy()
        else:
            for i in range(n):
                if i not in set(node[j][0] for j in range(level)):
                    new_node = node.copy()
                    new_node.append((i, level))
                    new_bound = bound(new_node, level + 1)
                    if new_bound < best_cost:
                        branch_and_bound(new_node, level + 1, min_cost, min_assignment)

    best_cost = float('inf')
    best_assignment = []
    branch_and_bound([], 0, best_cost, best_assignment)

    return best_cost, [(student, club) for (student, club) in best_assignment]

# Get user input for the cost matrix
n = int(input("Enter the number of students and clubs (N): "))
print("Enter the cost matrix:")
cost_matrix = []
for i in range(n):
    row = list(map(int, input().split()))
    if len(row) != n:
        print("Invalid input. Please enter a square matrix.")
        exit(1)
    cost_matrix.append(row)

min_cost, assignment = club_assignment_bnb(cost_matrix)
print(f"Minimum Cost: {min_cost}")
print("Assignment:")
for student, club in assignment:
    print(f"Student {student} to Club {club}")