Greedy অ্যালগরিদম আর exchange argument

১ · Greedy-র মূল ধারণা — এই মুহূর্তের সেরা পছন্দ

একটি greedy অ্যালগরিদম একটি optimization problem-এর সমাধান ধাপে ধাপে বানায়। প্রতিটি ধাপে কয়েকটি বিকল্পের মধ্যে একটি সরল নিয়মে “এখন সবচেয়ে ভালো” বিকল্পটি বেছে নেয়, আর সেই সিদ্ধান্ত আর কখনো বদলায় না। পর্ব ৫৬-এর backtracking-এর মতো ফিরে গিয়ে অন্য পথ চেষ্টা করে না, পর্ব ৫২-এর dynamic programming-এর মতো সব উপসমস্যার উত্তরও মনে রাখে না। তাই greedy সাধারণত খুব দ্রুত — প্রায়ই একটি সর্ট আর একটি লুপ, মোট O(n log n).

প্রশ্ন একটাই: স্থানীয়ভাবে সেরা পছন্দগুলো জুড়ে কি সামগ্রিকভাবে সেরা উত্তর হয়? সব সমস্যায় হয় না। দুটি ধর্ম থাকলে হয়:

Optimal substructure dynamic programming-এরও ভিত্তি। পার্থক্য হলো, DP সব সম্ভাব্য প্রথম পছন্দ চেষ্টা করে সেরাটি নেয়; greedy শুধু একটি নেয়, কারণ greedy-choice property বলে ওটিই যথেষ্ট। তাই greedy-র আসল কাজ হলো প্রমাণ: কেন ঠিক ওই একটি পছন্দই নিরাপদ।

Greedy নকশার তিন ধাপ

২ · Activity selection — এক রুমে সবচেয়ে বেশি ক্লাস

একটি কোচিং সেন্টারের একটিমাত্র সেমিনার রুম। আটজন শিক্ষক আজকের জন্য রুমটি চেয়েছেন, প্রত্যেকের নির্দিষ্ট শুরু আর শেষের সময় আছে। দুটি ক্লাস একসাথে চলতে পারে না, তবে একটি ১০টায় শেষ হলে আরেকটি ঠিক ১০টায় শুরু হতে পারে। প্রশ্ন: সবচেয়ে বেশি কয়টি ক্লাস রাখা যায়? এটিই বিখ্যাত activity selection বা interval scheduling সমস্যা। প্রতিটি ক্লাস একটি half-open interval [s, f) — শুরুর মুহূর্ত ভেতরে, শেষের মুহূর্ত বাইরে। দুটি ক্লাস মেলে না (compatible) যদি একটির f ≤ অন্যটির s.

চারটি স্বাভাবিক নিয়ম — তিনটিই ভুল

আমাদের আট ক্লাসেও “আগে শুরু” নিয়মটি ভোগায়: A (৮টা) নেয়, তারপর E (১০–১৪) — চার ঘণ্টার এই ক্লাস C আর D দুটোকেই খেয়ে ফেলে — তারপর G. মোট ৩টি। অথচ পাঁচটি সম্ভব। জয়ী নিয়মটি হলো earliest finish time first: সব ক্লাস শেষের সময় অনুযায়ী সাজান; যে ক্লাস শেষ নেওয়া ক্লাসের পরে শুরু হয়, তা নিন। স্বজ্ঞা: যে ক্লাস সবচেয়ে আগে শেষ হয়, সে রুমটি সবচেয়ে আগে খালি করে দেয় — বাকিদের জন্য সবচেয়ে বেশি সময় রেখে যায়।

Pseudocode — activity selection, earliest finish time (0-based)

SelectActivities(a[0..n-1]):          // a[i] = (s, f), half-open [s, f)
    sort a by finish time f            // O(n log n)
    chosen = [ ];  last = -infinity    // finish time of the last chosen one
    for each (s, f) in sorted order:
        if s >= last:                  // starts after the last chosen ends
            append (s, f) to chosen;  last = f
    return chosen

জটিলতা: সর্ট O(n log n), তারপর একবার স্ক্যান Θ(n) — মোট O(n log n) সময়। ক্লাসগুলো আগে থেকেই শেষের সময়ে সাজানো থাকলে Θ(n). জায়গা: সর্টের জন্য O(log n) থেকে O(n) (লাইব্রেরি অনুযায়ী) আর উত্তরের তালিকা O(n). সময়গুলো ছোট পূর্ণসংখ্যা হলে counting sort (পর্ব ২৪) দিয়ে পুরোটাই রৈখিক।

৩ · প্রমাণ — exchange argument আর “greedy stays ahead”

“আগে যে শেষ হয়” শুনতে যুক্তিসঙ্গত, কিন্তু “আগে শুরু” নিয়মও শুনতে যুক্তিসঙ্গত ছিল। পার্থক্য করে প্রমাণ। দুটি পদ্ধতিতেই একই সত্য প্রমাণ করা যায়; দুটিই শিখে রাখুন, কারণ বিভিন্ন সমস্যায় একটি অন্যটির চেয়ে সহজ হয়।

পদ্ধতি ১ — Exchange argument

প্রমাণ (exchange argument): যেকোনো একটি সর্বোত্তম সমাধান OPT নিন, তার ক্লাসগুলো শেষের সময়ে সাজান: o₁, o₂, …, o_k. যদি o₁ = g, কাজ শেষ। না হলে OPT′ = OPT − o₁ + g বানান। (১) g সবচেয়ে আগে শেষ হয়, তাই f(g) ≤ f(o₁). (২) o₁ আর o₂ মেলে না, তাই f(o₁) ≤ s(o₂). দুটি মিলে f(g) ≤ s(o₂) — g, o₂-এর সাথে (আর তার পরের সবার সাথে) মেলে না। তাই OPT′ বৈধ, আর তার আকারও k — সেটিও সর্বোত্তম, এবং তাতে g আছে। ∎

এরপর optimal substructure: g নেওয়ার পর বাকি সমস্যা হলো “যেসব ক্লাস f(g)-এর পরে শুরু হয়, তাদের মধ্যে সবচেয়ে বেশি”. Greedy ঠিক এই সমস্যাতেই আবার একই নিয়ম চালায়। ক্লাসের সংখ্যার ওপর induction করলে পুরো অ্যালগরিদম সর্বোত্তম। নিচে আমাদের উদাহরণেই বদলটি দেখুন — এখানে দুটি আলাদা সর্বোত্তম সমাধান আছে।

পদ্ধতি ২ — Greedy stays ahead

Greedy-র বাছাই g₁, …, g_m আর যেকোনো সর্বোত্তম সমাধান o₁, …, o_k, দুটিই শেষের সময়ে সাজানো। লক্ষ্য m = k. দাবি (greedy stays ahead): প্রতিটি r ≤ m-এর জন্য f(g_r) ≤ f(o_r).

1. Base case, r = 1: g₁ সব ক্লাসের মধ্যে সবচেয়ে আগে শেষ হয়, তাই f(g₁) ≤ f(o₁).
2. Inductive step: ধরুন f(g_r−1) ≤ f(o_r−1). o_r শুরু হয় o_r−1 শেষ হওয়ার পর: s(o_r) ≥ f(o_r−1) ≥ f(g_r−1). অর্থাৎ greedy যখন r-তম ক্লাস বাছছিল, o_r তখন বৈধ প্রার্থী ছিল। Greedy সবচেয়ে আগে শেষ হওয়া বৈধ প্রার্থীকে নেয়, তাই f(g_r) ≤ f(o_r).
3. উপসংহার: ধরুন k > m. তাহলে o_m+1 আছে, আর s(o_m+1) ≥ f(o_m) ≥ f(g_m) — greedy শেষ হওয়ার পরেও একটি বৈধ ক্লাস বাকি ছিল, অথচ greedy থেমে গেছে। বিরোধ। তাই k = m. ∎

৪ · কোডে activity selection — আর brute force দিয়ে যাচাই

প্রমাণ থাকলেও কোডে ভুল হতে পারে: ভুল key দিয়ে সর্ট, > আর >=-এর গোলমাল। তাই নিচের প্রোগ্রাম দুটি কাজ করে। প্রথমে greedy চালিয়ে প্রতিটি ক্লাসের জন্য take বা skip ছাপে। তারপর brute force: আটটি ক্লাসের সব 2⁸ = ২৫৬টি উপসেট দেখে, সংঘাতহীন উপসেটগুলোর মধ্যে সবচেয়ে বড়টির আকার বের করে। দুটি উত্তর মিললে ভরসা বাড়ে। ক্লাসগুলো ইচ্ছা করে এলোমেলো ক্রমে দেওয়া, যাতে সর্টটিও পরীক্ষিত হয়।

#include <algorithm>
#include <bit>
#include <cstdio>
#include <vector>
using namespace std;
struct Class { char name; int s, f; };                 // half-open [s, f)

vector<char> greedy(vector<Class> a) {                 // earliest finish time first
    sort(a.begin(), a.end(), [](const Class& x, const Class& y) { return x.f < y.f; });
    vector<char> chosen; int last = 0;                 // finish of the last chosen class
    for (const Class& c : a) {
        bool ok = c.s >= last;                         // touching is fine
        printf("  %s %c [%d,%d)\n", ok ? "take" : "skip", c.name, c.s, c.f);
        if (ok) { chosen.push_back(c.name); last = c.f; }
    }
    return chosen;
}
int brute(const vector<Class>& a, int& ways) {         // try all 2^n subsets
    int n = a.size(), best = 0; ways = 0;
    for (unsigned m = 0; m < (1u << n); ++m) {
        bool ok = true;
        for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j)
            if ((m >> i & 1) && (m >> j & 1) && a[i].s < a[j].f && a[j].s < a[i].f) ok = false;
        int k = popcount(m);
        if (ok && k > best) { best = k; ways = 1; } else if (ok && k == best) ++ways;
    }
    return best;
}
int main() {
    vector<Class> a = {{'E', 10, 14}, {'A', 8, 10}, {'G', 14, 16}, {'C', 11, 12},
                       {'H', 15, 17}, {'B', 9, 11}, {'F', 13, 15}, {'D', 12, 13}};
    vector<char> g = greedy(a);
    int ways, best = brute(a, ways);
    printf("greedy picks %zu:", g.size());
    for (char c : g) printf(" %c", c);
    printf("\nbrute force over %d subsets: best = %d (%d optimal sets)\n", 1 << a.size(), best, ways);
    puts((int)g.size() == best ? "match: yes" : "match: NO");
}

  take A [8,10)
  skip B [9,11)
  take C [11,12)
  take D [12,13)
  skip E [10,14)
  take F [13,15)
  skip G [14,16)
  take H [15,17)
greedy picks 5: A C D F H
brute force over 256 subsets: best = 5 (2 optimal sets)
match: yes

from itertools import combinations

def greedy(classes):                          # earliest finish time first
    chosen, last = [], 0                      # last = finish of the last chosen class
    for name, s, f in sorted(classes, key=lambda c: c[2]):
        ok = s >= last                        # half-open [s, f): touching is fine
        print(f"  {'take' if ok else 'skip'} {name} [{s},{f})")
        if ok:
            chosen.append(name)
            last = f
    return chosen

def brute(classes):                           # try all 2^n subsets
    best, ways = 0, 0
    for k in range(len(classes) + 1):
        for sub in combinations(classes, k):
            if all(a[1] >= b[2] or b[1] >= a[2] for a, b in combinations(sub, 2)):
                if k > best: best, ways = k, 1
                elif k == best: ways += 1
    return best, ways

classes = [("E", 10, 14), ("A", 8, 10), ("G", 14, 16), ("C", 11, 12),
           ("H", 15, 17), ("B", 9, 11), ("F", 13, 15), ("D", 12, 13)]
g = greedy(classes)
best, ways = brute(classes)
print(f"greedy picks {len(g)}:", " ".join(g))
print(f"brute force over {2 ** len(classes)} subsets: best = {best} ({ways} optimal sets)")
print("match: yes" if len(g) == best else "match: NO")

  take A [8,10)
  skip B [9,11)
  take C [11,12)
  take D [12,13)
  skip E [10,14)
  take F [13,15)
  skip G [14,16)
  take H [15,17)
greedy picks 5: A C D F H
brute force over 256 subsets: best = 5 (2 optimal sets)
match: yes

Stress testing — একটি ইনপুট যথেষ্ট নয়

একটি ইনপুটে মিল মানে শুধু ওই ইনপুটে ঠিক। আসল অভ্যাস হলো stress testing: একটি লুপে হাজার হাজার এলোমেলো ছোট ইনপুট (৬–১০টি interval, সময় ০–২০) বানান, প্রতিটিতে greedy আর brute force চালান, অমিল পেলেই ইনপুটটি ছেপে থামুন। ভুল greedy সাধারণত কয়েক সেকেন্ডেই ধরা পড়ে — “আগে শুরু” নিয়মটি প্রথম কয়েকটি ইনপুটেই হারবে। ছোট ইনপুট বাছার কারণ দুটি: brute force দ্রুত চলে, আর ভুল ধরা পড়লে ইনপুটটি হাতে trace করা যায়। কনটেস্টে wrong answer পেলে, বা AI-এর দেওয়া কোনো greedy-তে সন্দেহ হলে, এটিই প্রথম হাতিয়ার।

৫ · Interval partitioning — সব ক্লাসের জন্য কয়টি রুম লাগবে

এবার প্রশ্ন উল্টো। কোনো ক্লাস বাদ দেওয়া যাবে না — সবগুলো রাখতে হবে; প্রশ্ন হলো সবচেয়ে কম কয়টি রুম লাগবে? রেলস্টেশনে ট্রেনের জন্য প্ল্যাটফর্ম, হাসপাতালের অপারেশন থিয়েটার, পরীক্ষার হল — একই সমস্যা। একে বলে interval partitioning.

অ্যালগরিদম: ক্লাসগুলো শুরুর সময়ে সাজান। প্রতিটি ক্লাসের জন্য দেখুন, এমন কোনো রুম কি আছে যা এর শুরুর মধ্যে খালি হয়ে যায়? থাকলে সেখানে দিন; না থাকলে নতুন রুম খুলুন। “কোন রুম সবচেয়ে আগে খালি হয়” দ্রুত জানতে একটি min-heap (পর্ব ২৩) রাখুন, যাতে প্রতিটি রুমের (খালি হওয়ার সময়, রুম নম্বর) থাকে। নিচের উদাহরণে সাতটি ক্লাস, নম্বর ১–৭.

কেন ঠিক: ধরুন greedy মোট d টি রুম খুলেছে। শেষ (d-তম) রুমটি খোলা হয়েছিল একটি ক্লাস x-এর জন্য, কারণ তখন বাকি d − 1 টি রুমের প্রতিটি ব্যস্ত ছিল — প্রতিটিতে এমন একটি ক্লাস চলছিল যা x-এর আগে বা একই সময়ে শুরু হয়েছে (শুরুর ক্রমে সাজানো) আর s(x)-এর পরে শেষ হবে। তাহলে ঠিক s(x) মুহূর্তে x আর ওই d − 1 টি ক্লাস, মোট d টি ক্লাস একসাথে চলছে: depth ≥ d. আর যেকোনো সমাধানে লাগে ≥ depth. তাই greedy সর্বোত্তম। ∎ লক্ষ করুন, এই প্রমাণটি একটি তৃতীয় ধাঁচের: “একটি কাঠামোগত নিম্নসীমা খুঁজে দেখানো যে greedy সেটি ছুঁয়ে ফেলে”.

জটিলতা: সর্ট O(n log n), প্রতিটি ক্লাসে heap-এ একটি push আর সর্বোচ্চ একটি pop, প্রতিটি O(log n) — মোট O(n log n), জায়গা O(n). শুধু রুমের সংখ্যা দরকার হলে আরও সহজ একটি sweep line চলে: প্রতিটি ক্লাসকে দুটি ঘটনা বানান — শুরুতে +১, শেষে −১ — সময় অনুযায়ী সাজান, আর চলমান যোগফলের সর্বোচ্চ মানই উত্তর। সতর্কতা: একই সময়ে একটি শেষ আর একটি শুরু থাকলে half-open interval-এ −১ আগে প্রক্রিয়া করুন; না হলে উত্তর একটি বেশি আসবে — একটি ক্লাসিক off-by-one বাগ।

৬ · যেখানে greedy হারে — knapsack আর coin change

Fractional knapsack — ভাঙা গেলে greedy

চকবাজারের একজন মশলা ব্যবসায়ী ৫০ কেজির একটি বস্তা নিয়ে পাইকারি বাজারে গেছেন। তিন রকম মশলা পাওয়া যাচ্ছে, প্রতিটির পরিমাণ সীমিত। প্রশ্ন হলো, বস্তায় কোন মশলা কতটুকু ভরলে মোট দাম সবচেয়ে বেশি হয়। এটিই knapsack সমস্যা. মশলা ওজন করে যেকোনো পরিমাণে নেওয়া যায়, তাই এখানে রূপটি fractional knapsack.

Greedy: প্রতিটি জিনিসের value density, অর্থাৎ প্রতি কেজির দাম, বের করুন; বড় থেকে ছোট ক্রমে সাজান; যতক্ষণ জায়গা আছে পুরোটা নিন, শেষেরটির যতটুকু ধরে ততটুকু। এখানে পুরো এলাচ (১০ কেজি, ৬০), পুরো জিরা (২০ কেজি, ১০০), তারপর বাকি ২০ কেজি জায়গায় গোলমরিচের ২০/৩০ অংশ (৮০) — মোট ২৪০ হাজার টাকা. সময় O(n log n) (সর্ট), জায়গা O(n).

প্রমাণ (exchange): ধরুন একটি সর্বোত্তম ভরাট আছে, যাতে কোনো কম-ঘনত্বের জিনিস j-এর কিছু অংশ আছে, অথচ বেশি-ঘনত্বের জিনিস i পুরোটা নেওয়া হয়নি। j-এর ε কেজি সরিয়ে i-এর ε কেজি ভরুন: ওজন একই, দাম বদলায় ε · (ঘনত্ব_i − ঘনত্ব_j) ≥ ০. এভাবে বদলাতে বদলাতে ঠিক greedy-র ভরাটে পৌঁছানো যায়, দাম কখনো কমে না — তাই greedy-ও সর্বোত্তম। ∎ (George Dantzig ১৯৫৭ সালে knapsack-এর এই ভগ্নাংশ রূপের জন্য ঠিক এই ক্রমের সমাধান দেখান।)

0/1 knapsack — ভাঙা না গেলে greedy ভুল

এবার ধরুন মশলাগুলো সিলমোহর করা বস্তায় — হয় পুরো বস্তা নেবেন, নয়তো নেবেন না। এটি 0/1 knapsack. একই greedy প্রথমে এলাচ (১০ কেজি) আর জিরা (২০ কেজি) নেয় — ৩০ কেজি, ১৬০ হাজার। গোলমরিচের ৩০ কেজি আর ধরে না, তাই শেষ: ১৬০. অথচ জিরা + গোলমরিচ = ঠিক ৫০ কেজি, দাম ২২০. একটি counterexample — নিয়মটি বাতিল। “সবচেয়ে দামি আগে” বা “সবচেয়ে হালকা আগে” নিয়মেরও সহজ counterexample আছে। আসলে 0/1 knapsack NP-hard; কোনো দ্রুত greedy আশা করাই ভুল। সমাধান dynamic programming দিয়ে O(n · W) সময়ে (W = ধারণক্ষমতা) — একটি pseudo-polynomial অ্যালগরিদম, বিস্তারিত পর্ব ৫৩-এ।

কেন exchange প্রমাণটি এখানে ভেঙে পড়ে? প্রমাণে আমরা “j-এর ε কেজি সরিয়ে i-এর ε কেজি” ভরেছিলাম। জিনিস ভাঙা না গেলে ε-এর বদলে পুরো বস্তা বদলাতে হয়, আর তখন ওজন মেলে না — খালি জায়গা নষ্ট হয়। প্রমাণ কোথায় আটকায় তা দেখলেই বোঝা যায়, counterexample কোথায় খুঁজতে হবে।

Coin change — টাকার নোটে greedy, অদ্ভুত কয়েনে নয়

দোকানদার ১,৭৮৯ টাকা ফেরত দেবেন, যত কম সংখ্যক নোট ও কয়েনে সম্ভব। বাংলাদেশের মানগুলো ১, ২, ৫, ১০, ২০, ৫০, ১০০, ২০০, ৫০০ আর ১০০০ টাকা। প্রত্যেক দোকানদার না ভেবেই greedy চালান: যে সবচেয়ে বড় নোট ধরে, সেটি দিন, বাকিটার জন্য আবার একই কাজ। ১০০০ + ৫০০ + ২০০ + ৫০ + ২০ + ১০ + ৫ + ২ + ২ — মোট ৯টি। এটিই coin change সমস্যা। বাংলাদেশের টাকায় greedy সবসময় সবচেয়ে কম সংখ্যক নোট দেয় — যে coin system-এ এমন হয়, তাকে বলে canonical coin system.

কিন্তু ধরুন কোনো দেশে কয়েন শুধু ১, ৩ আর ৪ টাকার, আর ফেরত দিতে হবে ৬ টাকা। Greedy: ৪ + ১ + ১ = ৩টি কয়েন। অথচ ৩ + ৩ = মাত্র ২টি। এই system canonical নয়। সঠিক উত্তরের জন্য DP: dp[x] = x টাকা বানাতে সবচেয়ে কম কয়েন, আর dp[x] = ১ + min(dp[x − c]), যেখানে c প্রতিটি কয়েন ≤ x. সময় O(n · A) (n = কয়েনের রকম, A = অঙ্ক), জায়গা O(A).

নিচের প্রোগ্রাম দুটি coin system-এ প্রতিটি অঙ্কের জন্য greedy আর DP-র কয়েন-সংখ্যা মেলায়, আর প্রথম যে অঙ্কে greedy হারে তা দেখায়।

#include <cstdio>
#include <vector>
using namespace std;
const int INF = 1 << 30;

vector<int> greedy(const vector<int>& coins, int x) {      // coins sorted big -> small
    vector<int> used;
    for (int v : coins) while (x >= v) { x -= v; used.push_back(v); }
    return used;
}
void dpCoins(const vector<int>& coins, int A, vector<int>& dp, vector<int>& pick) {
    dp.assign(A + 1, INF); pick.assign(A + 1, 0); dp[0] = 0;   // dp[x] = fewest coins for x
    for (int x = 1; x <= A; ++x)
        for (int v : coins)
            if (v <= x && dp[x - v] + 1 < dp[x]) { dp[x] = dp[x - v] + 1; pick[x] = v; }
}
void check(const char* name, const vector<int>& coins, int A) {
    vector<int> dp, pick, bad;
    dpCoins(coins, A, dp, pick);
    for (int x = 1; x <= A; ++x) if ((int)greedy(coins, x).size() != dp[x]) bad.push_back(x);
    printf("%s amounts 1..%d: greedy wrong for %zu amounts\n", name, A, bad.size());
    if (bad.empty()) return;
    int x = bad[0];
    vector<int> g = greedy(coins, x);
    printf("  first failure %d: greedy", x);
    for (int v : g) printf(" %d", v);
    printf(" (%zu coins), optimal", g.size());
    for (int y = x; y > 0; y -= pick[y]) printf(" %d", pick[y]);
    printf(" (%d coins)\n", dp[x]);
}
int main() {
    vector<int> taka = {1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
    vector<int> used = greedy(taka, 1789);
    printf("1789 taka -> %zu notes:", used.size());
    for (int v : used) printf(" %d", v);
    puts("");
    check("taka", taka, 2000);
    check("{1,3,4}", {4, 3, 1}, 20);
}

1789 taka -> 9 notes: 1000 500 200 50 20 10 5 2 2
taka amounts 1..2000: greedy wrong for 0 amounts
{1,3,4} amounts 1..20: greedy wrong for 4 amounts
  first failure 6: greedy 4 1 1 (3 coins), optimal 3 3 (2 coins)

INF = float("inf")

def greedy(coins, x):                         # coins sorted big -> small
    used = []
    for v in coins:
        while x >= v:
            x -= v
            used.append(v)
    return used

def dp_coins(coins, A):                       # dp[x] = fewest coins that make x
    dp, pick = [0] + [INF] * A, [0] * (A + 1)
    for x in range(1, A + 1):
        for v in coins:
            if v <= x and dp[x - v] + 1 < dp[x]:
                dp[x], pick[x] = dp[x - v] + 1, v
    return dp, pick

def check(name, coins, A):
    dp, pick = dp_coins(coins, A)
    bad = [x for x in range(1, A + 1) if len(greedy(coins, x)) != dp[x]]
    print(f"{name} amounts 1..{A}: greedy wrong for {len(bad)} amounts")
    if bad:
        x, best = bad[0], []
        y = x
        while y:
            best.append(pick[y]); y -= pick[y]
        g = greedy(coins, x)
        print(f"  first failure {x}: greedy", *g, f"({len(g)} coins), optimal", *best, f"({len(best)} coins)")

taka = [1000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
used = greedy(taka, 1789)
print(f"1789 taka -> {len(used)} notes:", *used)
check("taka", taka, 2000)
check("{1,3,4}", [4, 3, 1], 20)

1789 taka -> 9 notes: 1000 500 200 50 20 10 5 2 2
taka amounts 1..2000: greedy wrong for 0 amounts
{1,3,4} amounts 1..20: greedy wrong for 4 amounts
  first failure 6: greedy 4 1 1 (3 coins), optimal 3 3 (2 coins)

কতদূর পরীক্ষা করলে যথেষ্ট? ১ থেকে ২০০০ পরীক্ষা করে কি “সব অঙ্কে” বলা যায়? যায়, একটি জানা ফলের জোরে: Kozen ও Zaks (১৯৯৪) দেখান, কোনো coin system canonical না হলে সবচেয়ে ছোট counterexample অঙ্কটি সবচেয়ে বড় দুটি কয়েনের যোগফলের চেয়ে ছোট। টাকায় সেটি ১০০০ + ৫০০ = ১৫০০, তাই ২০০০ পর্যন্ত মিল পুরো system-এর প্রমাণ। {1, 3, 4}-এ সীমা ৪ + ৩ = ৭, আর ৬ সেই সীমার ভেতরেই। পরে David Pearson (২০০৫) একটি coin system canonical কি না তা O(n³) সময়ে যাচাইয়ের অ্যালগরিদম দেন। আর কয়েনের মানগুলোই যদি ইনপুটের অংশ হয়, তবে সাধারণ change-making সমস্যা NP-hard — DP-র O(n · A) বড় A-তে দ্রুত নয়।

৭ · Deadline-এর সমস্যা — lateness কমানো আর লাভের কাজ বাছাই

Minimising lateness — earliest deadline first

একটি ছাপাখানায় একটিই মেশিন। চারটি অর্ডার এসেছে; প্রতিটির ছাপার সময় t আর ডেলিভারির deadline d জানা (এখন থেকে ঘণ্টায়)। সব কাজ করতেই হবে, একটির পর একটি। যে কাজ deadline-এর পরে শেষ হয়, তার lateness = শেষ হওয়ার সময় − d (আগে শেষ হলে ০)। লক্ষ্য: সবচেয়ে বেশি lateness যতটা সম্ভব কম রাখা — কোনো গ্রাহককেই যেন বেশিক্ষণ অপেক্ষা না করতে হয়।

নিয়মটি হলো earliest deadline first (EDF): deadline-এর ক্রমে কাজ করুন, কাজের দৈর্ঘ্য দেখবেন না। উপরের সময়সূচিতে সর্বোচ্চ lateness ২, আর এর চেয়ে ভালো অসম্ভব: মোট কাজ ১০ ঘণ্টার, তাই শেষ কাজটি ১০-এ শেষ হবেই, আর কোনো deadline ৮-এর বেশি নয়। দুটি “স্বাভাবিক” বিকল্প নিয়ম ভুল: ছোট কাজ আগে — (t = ১, d = ১০০) আর (t = ১০, d = ১০): ছোটটি আগে করলে বড়টি ১ ঘণ্টা দেরি, EDF-এ কেউ দেরি নয়। সবচেয়ে কম ঢিল (d − t) আগে — (t = ১, d = ২) আর (t = ১০, d = ১০): ঢিল-নিয়মে বড়টি আগে, ছোটটি ৯ ঘণ্টা দেরি; EDF-এ মাত্র ১.

প্রমাণ (inversion দিয়ে exchange): একটি সময়সূচিতে inversion মানে এমন দুটি কাজ i আর j, যেখানে d_i < d_j অথচ j আগে চলে। মাঝে কোনো ফাঁকা সময় নেই এমন একটি সর্বোত্তম সময়সূচি নিন।

1. Inversion থাকলে অন্তত একটি পাশাপাশি inversion আছে: পরপর দুটি কাজ j, i, যেখানে d_i < d_j. (পরপর প্রতিটি জোড়া deadline-এর ক্রমে থাকলে পুরো ক্রমটাই সাজানো হতো।)
2. দুটির জায়গা বদলান। বাকি সব কাজ একই সময়ে শেষ হয়। i আগে শেষ হয়, তার lateness বাড়ে না।
3. j এখন শেষ হয় ঠিক সেই সময়ে f, যখন আগে i শেষ হতো। তাই j-এর নতুন lateness = f − d_j < f − d_i = i-এর পুরোনো lateness. সর্বোচ্চ lateness তাই বাড়ে না।
4. প্রতি বদলে inversion ঠিক একটি কমে; সর্বোচ্চ n(n − 1)/2 বদলে কোনো inversion থাকে না — সেটিই EDF-এর সময়সূচি (সমান deadline-এর কাজগুলোর নিজেদের ক্রম সর্বোচ্চ lateness বদলায় না)। ∎

সময় O(n log n) — শুধু deadline দিয়ে সর্ট। এই নিয়মটি J. R. Jackson-এর নামে “Jackson-এর নিয়ম” বলেও পরিচিত (১৯৫৫)।

Job sequencing with deadlines — লাভ সবচেয়ে বেশি

অন্য রূপ: প্রতিটি কাজ ঠিক এক দিন নেয়, প্রতিটির একটি deadline (দিন) আর লাভ আছে; deadline-এর মধ্যে শেষ হলে লাভ মেলে, না হলে কাজটি নেওয়ারই দরকার নেই। এটি job sequencing with deadlines. Greedy: লাভের বড় থেকে ছোট ক্রমে কাজ দেখুন; প্রতিটিকে তার deadline-এর মধ্যে সবচেয়ে শেষের খালি দিনে বসান, খালি দিন না থাকলে বাদ। শেষের দিনে বসানোর কারণ: আগের দিনগুলো খালি রাখা, যাতে ছোট deadline-এর কাজগুলো জায়গা পায়।

ফল: দিন ১-এ c, দিন ২-এ a, দিন ৩-এ e — মোট লাভ ১৪২. প্রতিটি কাজের জন্য পেছনে হেঁটে খালি দিন খুঁজলে O(n log n + n · D) (D = সবচেয়ে বড় deadline); “প্রতিটি দিনের আগের সবচেয়ে কাছের খালি দিন” DSU-তে (পর্ব ৩৩) রাখলে প্রায় O(n log n). এই greedy কেন ঠিক, তার সবচেয়ে পরিষ্কার ব্যাখ্যা matroid — পরের অংশে।

৮ · Greedy-র বড় পরিবার — MST, Dijkstra, Huffman আর matroid

এই কোর্সে আপনি আগেই কয়েকটি বিখ্যাত greedy দেখেছেন, হয়তো সেভাবে না ভেবে:

লক্ষ করুন, Dijkstra-ও ঋণাত্মক edge-এ ভুল করে — greedy-র নিশ্চয়তা সবসময় কিছু অনুমানের ওপর দাঁড়িয়ে (এখানে: edge-এর ওজন ঋণাত্মক নয়)। প্রমাণের কোন বাক্যে অনুমানটি লাগছে, তা জানলেই বোঝা যায় কোথায় greedy ভাঙবে।

Matroid একটি সুন্দর তত্ত্ব, কিন্তু সব greedy-কে ব্যাখ্যা করে না — যেমন activity selection-এর সংঘাতহীন সেটগুলো matroid নয়, তবু নির্দিষ্ট “আগে শেষ” নিয়মে greedy ঠিক। তাই বাস্তবে প্রতিটি নতুন greedy-র জন্য সরাসরি exchange বা stays ahead প্রমাণই সবচেয়ে নির্ভরযোগ্য পথ।

৯ · AI-এর যুগে greedy — শুনতে ঠিক, প্রমাণ ছাড়া বিপজ্জনক

Greedy AI-এর সবচেয়ে প্রিয় ফাঁদ। “সাজাও আর লুপ চালাও” ধরনের সমাধান লেখা সহজ, পড়তেও বিশ্বাসযোগ্য, আর ছোট উদাহরণে প্রায়ই ঠিক উত্তর দেয়। AI সহকারীরা প্রায়ই একটি greedy প্রস্তাব করে, সাথে আত্মবিশ্বাসী একটি “প্রমাণ”-ও দেয়, যার কোনো একটি বাক্য আসলে মিথ্যা। কনটেস্টে এর ফল wrong answer, ইন্টারভিউতে “why is this correct?” প্রশ্নে আটকে যাওয়া।

Greedy-তে AI সাধারণত যেসব ভুল করে

Greedy যাচাইয়ের চেকলিস্ট

• অন্তত তিনটি বিকল্প নিয়ম লিখে প্রতিটির জন্য ছোট counterexample খুঁজেছি
• যে নিয়মটি রাখলাম, তার জন্য exchange বা stays ahead প্রমাণ লিখেছি — “স্পষ্টতই” শব্দ ছাড়া
• ছোট এলোমেলো ইনপুটে brute force-এর সাথে হাজারবার মিলিয়েছি (stress testing)
• Edge case: খালি ইনপুট, একটি উপাদান, সব সমান, ঠিক ছুঁয়ে যাওয়া interval, সমান key-এর tie-break
• Complexity-তে সর্ট আর ডেটা স্ট্রাকচারের খরচ ধরেছি; বড় যোগফলে long long
• সমস্যার রূপ আবার পড়েছি — ভগ্নাংশ চলে কি না, সব কাজ রাখতে হবে কি না, কয়েন system কী