ব্রাঞ্চ-অ্যান্ড-বাউন্ড প্যারাডাইম

import itertools

def knapsack_branch_and_bound(weights, values, capacity):
    n = len(weights)
    # value/weight অনুপাত অনুযায়ী সাজানো -- ফ্র্যাকশনাল রিল্যাক্সেশন বাউন্ডের জন্য দরকার (L22-এর গ্রিডি)
    order = sorted(range(n), key=lambda i: values[i] / weights[i], reverse=True)
    w = [weights[i] for i in order]
    v = [values[i] for i in order]

    best_value = 0
    nodes_explored = 0
    pruned_infeasible = 0
    pruned_bound = 0

    def bound(index, current_weight, current_value):
        # বাকি ক্যাপাসিটি আইটেমগুলো ভগ্নাংশে নেওয়ার অনুমতি দিলে সর্বোচ্চ কত মূল্য সম্ভব -- একটি আশাবাদী (upper) বাউন্ড
        if current_weight > capacity:
            return 0
        result = current_value
        remaining = capacity - current_weight
        i = index
        while i < n and w[i] <= remaining:
            remaining -= w[i]
            result += v[i]
            i += 1
        if i < n:
            result += v[i] * remaining / w[i]  # শেষ আইটেমের একটি ভগ্নাংশ
        return result

    def backtrack(index, current_weight, current_value):
        nonlocal best_value, nodes_explored, pruned_infeasible, pruned_bound
        nodes_explored += 1
        if current_weight > capacity:
            pruned_infeasible += 1  # প্রুন ধরন ১: ফিজিবিলিটি (L36-L37 স্টাইল)
            return
        best_value = max(best_value, current_value)
        if index == n:
            return
        b = bound(index, current_weight, current_value)
        if b <= best_value:
            pruned_bound += 1        # প্রুন ধরন ২: এই নতুন, বাউন্ড-ভিত্তিক প্রুনিং
            return
        backtrack(index + 1, current_weight + w[index], current_value + v[index])  # আইটেম নাও
        backtrack(index + 1, current_weight, current_value)                        # আইটেম বাদ দাও

    backtrack(0, 0, 0)
    return best_value, nodes_explored, pruned_infeasible, pruned_bound


def brute_force_knapsack(weights, values, capacity):
    n = len(weights)
    best = 0
    for r in range(n + 1):
        for combo in itertools.combinations(range(n), r):
            tw = sum(weights[i] for i in combo)
            tv = sum(values[i] for i in combo)
            if tw <= capacity and tv > best:
                best = tv
    return best


weights = [2, 3, 4, 5, 9, 7, 1, 6]
values = [3, 4, 5, 8, 10, 6, 2, 9]
capacity = 15
n = len(weights)

bb_value, nodes, pruned_infeasible, pruned_bound = knapsack_branch_and_bound(weights, values, capacity)
bf_value = brute_force_knapsack(weights, values, capacity)

print("ব্রুট-ফোর্স অপটিমাম:      ", bf_value)
print("ব্রাঞ্চ-অ্যান্ড-বাউন্ড অপটিমাম:", bb_value)
print("দুটো মিলল কিনা:            ", bb_value == bf_value)
print()
print("সার্চ ট্রি-র সম্পূর্ণ (বাইনারি) নোড সংখ্যা:", 2 ** (n + 1) - 1)
print("প্রকৃতপক্ষে এক্সপ্লোর করা নোড:            ", nodes)
print("  -- ফিজিবিলিটির কারণে প্রুন হয়েছে:       ", pruned_infeasible)
print("  -- বাউন্ড তুলনার কারণে প্রুন হয়েছে:      ", pruned_bound)