ফ্র্যাকশনাল ন্যাপস্যাক

১ · সমস্যাটি আনুষ্ঠানিকভাবে

$n$টি আইটেম দেওয়া আছে, প্রতিটির একটি ভ্যালু $v_i$ ও ওজন $w_i$, এবং একটি ব্যাগের ধারণক্ষমতা $W$। আইটেমগুলো ফ্র্যাকশনালি নেওয়া যায় — অর্থাৎ একটি আইটেমের যেকোনো অংশ (যেমন $0.4$ অংশ) নেওয়া সম্ভব, এবং সেই অংশের ভ্যালু ও ওজন সমানুপাতিকভাবে কমে যায়। লক্ষ্য: মোট ওজন $W$-এর বেশি না হয়ে মোট ভ্যালু সর্বোচ্চ করা।

$$\text{maximize } \sum_i x_i v_i \quad \text{subject to} \quad \sum_i x_i w_i \le W, \quad 0 \le x_i \le 1$$

এখানে $x_i$ হলো $i$-তম আইটেমের কতটুকু অংশ নেওয়া হয়েছে ($x_i=1$ মানে পুরোটা, $x_i=0.5$ মানে অর্ধেক)। এই মেকানিক্স DSA কোর্সে ইতিমধ্যে কভার করা হয়েছে — এখানে আমরা মনোযোগ দেব কেন "সবচেয়ে বেশি $v_i/w_i$ অনুপাতের আইটেম আগে নাও" নিয়মটি প্রমাণযোগ্যভাবে অপটিমাল।

২ · এক্সচেঞ্জ আর্গুমেন্ট — রেশিও-অর্ডারিং কেন সঠিক

ধরি আইটেমগুলো রেশিও অনুযায়ী নামিয়ে সাজানো: $\frac{v_1}{w_1} \ge \frac{v_2}{w_2} \ge \dots \ge \frac{v_n}{w_n}$। দাবি: গ্রিডি (রেশিও-অর্ডারে সবচেয়ে বেশি রেশিওর আইটেম থেকে যতটা সম্ভব নেওয়া) সবসময় অপটিমাল।

1. ধরে নাও: $S$ একটি অপটিমাল সমাধান যা আইটেম ১ (সবচেয়ে বেশি রেশিও) থেকে গ্রিডির চেয়ে কম অংশ নিয়েছে (যদি $S$ ইতিমধ্যে গ্রিডির মতোই আইটেম ১ থেকে সর্বোচ্চ সম্ভব অংশ নিয়ে থাকে, প্রমাণ শেষ)।
2. বদলাও (exchange): যেহেতু $S$ আইটেম ১-এর পুরোটা নেয়নি অথচ ধারণক্ষমতা ব্যবহার হয়ে গেছে (নাহলে আরও আইটেম-১ যোগ করা যেত, যা শুধু ভ্যালু বাড়াতোই), তার মানে $S$ অন্য কোনো আইটেম $j$ (যার রেশিও $\le$ আইটেম ১-এর রেশিও) থেকে কিছু অংশ নিয়েছে। সামান্য পরিমাণ $\epsilon$ ওজন আইটেম $j$ থেকে সরিয়ে আইটেম ১-এ যোগ করো (ওজন অপরিবর্তিত থাকে, তাই এখনও বৈধ)।
3. দেখাও কোনো ক্ষতি হয়নি: এই বদলে ভ্যালুর পরিবর্তন হলো $\epsilon \cdot \frac{v_1}{w_1} - \epsilon \cdot \frac{v_j}{w_j} \ge 0$ (কারণ $\frac{v_1}{w_1} \ge \frac{v_j}{w_j}$) — অর্থাৎ মোট ভ্যালু কমেনি, বরং সমান বা বেড়েছে। সুতরাং নতুন সমাধান $S'$-ও অপটিমাল (অথবা আরও ভালো, যা অপটিমালিটির স্ববিরোধ — তাই আসলে সমান হতে হবে)।
4. ইনডাকশন: এই বদল বারবার প্রয়োগ করলে (প্রতিবার আইটেম ১-এ আরও অংশ সরিয়ে) শেষ পর্যন্ত $S'$ ঠিক গ্রিডির মতোই আইটেম ১ থেকে সর্বোচ্চ সম্ভব অংশ নেবে, ভ্যালু না কমিয়ে। অবশিষ্ট ধারণক্ষমতার জন্য একই যুক্তি বাকি আইটেমগুলোর (রেশিও-ক্রমে) উপর পুনরাবৃত্ত করলে সম্পূর্ণ গ্রিডি সমাধানই অপটিমাল প্রমাণিত হয়।

লক্ষ করুন ধাপ ২-৩-এ $\epsilon$ পরিমাণ ওজন ভেঙে সরানো সম্ভব হয়েছে শুধু কারণ আইটেমগুলো ফ্র্যাকশনালি ভাঙা যায় — এটাই সেই জায়গা যেখানে 0/1 ন্যাপস্যাকে এই প্রমাণ ভেঙে পড়ে (নিচে ৪ নং সেকশনে)।

৩ · কম্পিউটেশনাল যাচাই — রেশিও বনাম দুটি ভুল অর্ডারিং

যেহেতু আইটেমগুলো ভাঙা যায়, তাই এখানে ব্রুট-ফোর্স এক্সহস্টিভ সার্চের দরকার নেই যেমন L20-তে ছিল — বরং আমরা রেশিও-গ্রিডিকে দুটি ইচ্ছাকৃতভাবে ভুল "কী" (sorting key) দিয়ে সাজানো গ্রিডির বিপরীতে তুলনা করব: (ক) শুধু ওজন অনুযায়ী (হালকা আইটেম আগে), এবং (খ) শুধু ভ্যালু অনুযায়ী (বেশি-দামি আইটেম আগে, ওজন উপেক্ষা করে)। প্রমাণ অনুযায়ী, রেশিও-গ্রিডি কখনোই এই দুটোর চেয়ে খারাপ ফলাফল দিতে পারবে না।

import random

def knapsack_greedy(items, capacity, key):
    # items: (value, weight) জোড়ার লিস্ট; key(item) অনুযায়ী নামিয়ে সাজিয়ে যতটা সম্ভব নেওয়া হয়
    order = sorted(items, key=key, reverse=True)
    remaining = capacity
    total_value = 0.0
    for value, weight in order:
        if remaining <= 0:
            break
        take = min(weight, remaining)
        fraction = take / weight
        total_value += fraction * value
        remaining -= take
    return total_value

def by_ratio(item):
    value, weight = item
    return value / weight        # সঠিক কী -- এক্সচেঞ্জ আর্গুমেন্ট দিয়ে প্রমাণিত

def by_weight_ascending(item):
    value, weight = item
    return -weight                # ভুল কী -- শুধু হালকা আইটেম আগে, ভ্যালু উপেক্ষিত

def by_value_alone(item):
    value, weight = item
    return value                  # ভুল কী -- শুধু বেশি-দামি আইটেম আগে, ওজন উপেক্ষিত

random.seed(11)
trials = 25
strictly_better_count = 0
for trial in range(trials):
    n = random.randint(2, 8)
    items = [(random.randint(1, 100), random.randint(1, 50)) for _ in range(n)]
    capacity = random.randint(10, 150)

    ratio_value = knapsack_greedy(items, capacity, key=by_ratio)
    weight_value = knapsack_greedy(items, capacity, key=by_weight_ascending)
    value_value = knapsack_greedy(items, capacity, key=by_value_alone)

    # প্রমাণের দাবি: রেশিও-গ্রিডি কখনো ভুল-কী অর্ডারিংয়ের চেয়ে খারাপ হবে না
    assert ratio_value >= weight_value - 1e-9, (items, capacity, ratio_value, weight_value)
    assert ratio_value >= value_value - 1e-9, (items, capacity, ratio_value, value_value)

    if ratio_value > weight_value + 1e-9 or ratio_value > value_value + 1e-9:
        strictly_better_count += 1

print(f"মোট ট্রায়াল: {trials}")
print(f"রেশিও-গ্রিডি কখনো ভুল-কী অর্ডারিংয়ের চেয়ে খারাপ হয়নি: নিশ্চিত (সব assert পাস)")
print(f"যেসব ট্রায়ালে রেশিও-গ্রিডি কমপক্ষে একটি ভুল-কী অর্ডারিংয়ের চেয়ে কঠোরভাবে ভালো ফল দিয়েছে: {strictly_better_count}/{trials}")

# একটি নির্দিষ্ট উদাহরণ
example_items = [(60, 10), (100, 20), (120, 30)]   # (value, weight)
example_capacity = 50
print("\nউদাহরণ আইটেম (value, weight):", example_items, "| ক্ষমতা:", example_capacity)
print("  রেশিও-গ্রিডি ভ্যালু:      ", knapsack_greedy(example_items, example_capacity, key=by_ratio))
print("  শুধু-ওজন-গ্রিডি ভ্যালু:   ", knapsack_greedy(example_items, example_capacity, key=by_weight_ascending))
print("  শুধু-ভ্যালু-গ্রিডি ভ্যালু:", knapsack_greedy(example_items, example_capacity, key=by_value_alone))

৪ · কেন এটি 0/1 ন্যাপস্যাকে কাজ করে না

যদি আইটেম ভাঙা না যায় (প্রতিটি আইটেম হয় পুরোটা নাও, নয়তো একদমই না — এটাই 0/1 ন্যাপস্যাক, M6/L25-এ বিস্তারিত), তাহলে উপরের প্রমাণের ধাপ ২ ভেঙে পড়ে: $\epsilon$ পরিমাণ ওজন "সরিয়ে" এক আইটেম থেকে আরেক আইটেমে দেওয়ার সুযোগ নেই, কারণ আইটেম আংশিকভাবে নেওয়াই অসম্ভব। ফলে সবচেয়ে বেশি রেশিওর আইটেম প্রথমে নিলেও পরে ধারণক্ষমতার একটি বিশ্রী অংশ (leftover capacity) অব্যবহৃত থেকে যেতে পারে যা অন্য কোনো ছোট-রেশিও আইটেম দিয়ে ভালোভাবে পূরণ করা যেত — এবং এই সম্ভাবনা প্রমাণ করে দেয় গ্রিডি-চয়েস প্রপার্টি এখানে সাধারণভাবে সত্য নয়। 0/1 ন্যাপস্যাকের জন্য তাই DP (M6/L25) দরকার হয়, যা প্রতিটি সম্ভাব্য leftover capacity-র জন্য আলাদাভাবে সেরা সাবসেট বিবেচনা করে।