import heapq
from collections import namedtuple

Item = namedtuple('Item', ['value', 'weight'])

class Node:
    def __init__(self, level, profit, weight, bound, taken):
        self.level = level          # index of the item considered
        self.profit = profit        # profit so far
        self.weight = weight        # weight so far
        self.bound = bound          # upper bound of profit reachable
        self.taken = taken[:]       # list of booleans indicating taken items
    def __lt__(self, other):
        # heapq is a min‑heap; we want max‑bound first
        return self.bound > other.bound

def bound(node, capacity, items):
    if node.weight >= capacity:
        return 0
    profit_bound = node.profit
    j = node.level + 1
    totweight = node.weight
    # take items fractionally (fractional knapsack) to compute upper bound
    while j < len(items) and totweight + items[j].weight <= capacity:
        totweight += items[j].weight
        profit_bound += items[j].value
        j += 1
    if j < len(items):
        profit_bound += (capacity - totweight) * items[j].value / items[j].weight
    return profit_bound

def branch_and_bound_knapsack(items, capacity):
    # sort items by value/weight decreasing (helps bound quality)
    items = sorted(items, key=lambda i: i.value / i.weight, reverse=True)
    Q = []
    root = Node(-1, 0, 0, 0, [False]*len(items))
    root.bound = bound(root, capacity, items)
    heapq.heappush(Q, root)
    max_profit = 0
    best_taken = []
    while Q:
        node = heapq.heappop(Q)
        if node.bound <= max_profit:
            continue  # prune
        if node.level == len(items) - 1:
            continue
        # Branch: take next item
        nxt = node.level + 1
        taken_node = Node(nxt, node.profit + items[nxt].value,
                          node.weight + items[nxt].weight,
                          0, node.taken)
        taken_node.taken[nxt] = True
        if taken_node.weight <= capacity and taken_node.profit > max_profit:
            max_profit = taken_node.profit
            best_taken = taken_node.taken[:]
        taken_node.bound = bound(taken_node, capacity, items)
        if taken_node.bound > max_profit:
            heapq.heappush(Q, taken_node)
        # Branch: do NOT take next item
        not_taken_node = Node(nxt, node.profit, node.weight, 0, node.taken)
        not_taken_node.bound = bound(not_taken_node, capacity, items)
        if not_taken_node.bound > max_profit:
            heapq.heappush(Q, not_taken_node)
    return max_profit, best_taken

# Example usage
items = [Item(60, 10), Item(100, 20), Item(120, 30)]
capacity = 50
profit, selection = branch_and_bound_knapsack(items, capacity)
print(f"Maximum profit: {profit}")
print(f"Items taken: {selection}")

#include <bits/stdc++.h>
using namespace std;

struct Node {
    vector<int> path;      // visited cities in order
    double cost;           // cost so far
    double bound;          // lower bound (cost + MST of unvisited)
    vector<bool> visited; // city visited flags
    bool operator<(const Node& other) const {
        // priority_queue is max‑heap; we need smallest bound first
        return bound > other.bound;
    }
};

// Compute Euclidean distance matrix
vector<vector<double>> distanceMatrix(const vector<pair<double,double>>& pts) {
    int n = pts.size();
    vector<vector<double>> d(n, vector<double>(n, 0));
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            d[i][j] = hypot(pts[i].first-pts[j].first, pts[i].second-pts[j].second);
    return d;
}

// Simple Prim's algorithm to compute MST weight of a set of vertices
double mstWeight(const vector<int>& vertices, const vector<vector<double>>& dist) {
    if (vertices.empty()) return 0.0;
    unordered_set<int> inMST;
    unordered_set<int> notInMST(vertices.begin(), vertices.end());
    int start = *notInMST.begin();
    inMST.insert(start);
    notInMST.erase(start);
    double total = 0.0;
    while (!notInMST.empty()) {
        double best = numeric_limits<double>::infinity();
        int bestV = -1;
        for (int u : inMST) {
            for (int v : notInMST) {
                if (dist[u][v] < best) {
                    best = dist[u][v];
                    bestV = v;
                }
            }
        }
        total += best;
        inMST.insert(bestV);
        notInMST.erase(bestV);
    }
    return total;
}

double lowerBound(const Node& node, const vector<vector<double>>& dist, int n) {
    // cost so far + MST of remaining + return to start
    vector<int> remaining;
    for (int i=0;i<n;i++) if (!node.visited[i]) remaining.push_back(i);
    double mst = mstWeight(remaining, dist);
    double minReturn = numeric_limits<double>::infinity();
    if (!node.path.empty()) {
        int last = node.path.back();
        for (int v : remaining) minReturn = min(minReturn, dist[last][v]);
    } else {
        minReturn = 0; // root node
    }
    double minToStart = numeric_limits<double>::infinity();
    for (int v : remaining) minToStart = min(minToStart, dist[v][0]);
    return node.cost + mst + minReturn + minToStart;
}

pair<double, vector<int>> branchAndBoundTSP(const vector<pair<double,double>>& points) {
    int n = points.size();
    auto dist = distanceMatrix(points);
    priority_queue<Node> pq;
    Node root;
    root.path = {0};
    root.cost = 0;
    root.visited = vector<bool>(n,false);
    root.visited[0]=true;
    root.bound = lowerBound(root, dist, n);
    pq.push(root);
    double bestCost = numeric_limits<double>::infinity();
    vector<int> bestPath;
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        if (cur.bound >= bestCost) continue; // prune
        if (cur.path.size() == n) {
            // close the tour
            double tourCost = cur.cost + dist[cur.path.back()][0];
            if (tourCost < bestCost) {
                bestCost = tourCost;
                bestPath = cur.path;
                bestPath.push_back(0);
            }
            continue;
        }
        int last = cur.path.back();
        for (int nxt=0; nxt<n; ++nxt) if (!cur.visited[nxt]) {
            Node child = cur;
            child.path.push_back(nxt);
            child.cost += dist[last][nxt];
            child.visited[nxt]=true;
            child.bound = lowerBound(child, dist, n);
            if (child.bound < bestCost) pq.push(child);
        }
    }
    return {bestCost, bestPath};
}

int main(){
    vector<pair<double,double>> cities = {{0,0},{2,3},{5,4},{1,6},{7,2}}; // sample points
    auto [cost, tour] = branchAndBoundTSP(cities);
    cout << "Optimal tour cost: " << cost << "\nPath: ";
    for (int v: tour) cout << v << " ";
    cout << endl;
    return 0;
}