0/1 ন্যাপস্যাক প্রবলেম

১ · সমস্যার সংজ্ঞা

$n$টি আইটেম দেওয়া আছে, প্রতিটির একটি ওজন $w_i$ ও মূল্য $v_i$, এবং একটি ব্যাগের ধারণক্ষমতা $W$। লক্ষ্য: একটি উপসেট বেছে নেওয়া যার মোট ওজন $W$-এর বেশি না হয়ে মোট মূল্য সর্বোচ্চ হয় — কিন্তু প্রতিটি আইটেম হয় সম্পূর্ণ নেওয়া, নয়তো একদমই বাদ দেওয়া (তাই নাম "0/1")। এটি DSA কোর্সে ইতিমধ্যে একটি ক্লাসিক DP উদাহরণ হিসেবে ইমপ্লিমেন্ট করা হয়েছে — এখানে আমরা এর সঠিকতার পেছনের যুক্তি এবং একটি সত্যিকারের ব্রুট-ফোর্স-বনাম-DP যাচাইয়ে মনোযোগ দেব।

২ · DP রিকারেন্স ও অপটিমাল সাবস্ট্রাকচার

$dp[i][w]$ সংজ্ঞায়িত করি প্রথম $i$টি আইটেম (ইনডেক্স $1$ থেকে $i$) থেকে বেছে, ধারণক্ষমতা $w$-এর মধ্যে থেকে পাওয়া সর্বোচ্চ মূল্য হিসেবে। বেস কেস: $dp[0][w] = 0$ (কোনো আইটেম নেই মানে মূল্যও নেই)।

$$ dp[i][w] = \begin{cases} 0 & i = 0 \\ dp[i-1][w] & w_i > w \\ \max\big(\,dp[i-1][w],\;\; v_i + dp[i-1][w-w_i]\,\big) & \text{অন্যথায়} \end{cases} $$

উত্তর: $dp[n][W]$। রিকারেন্সের যুক্তি সহজ — $i$-তম আইটেম নিয়ে সিদ্ধান্ত নিতে দুটি বিকল্প আছে: (ক) বাদ দেওয়া — তাহলে সমস্যাটি ঠিক প্রথম $i-1$টি আইটেম নিয়ে একই ধারণক্ষমতা $w$-এর সাবপ্রবলেমে পরিণত হয়, অর্থাৎ $dp[i-1][w]$; অথবা (খ) নেওয়া (শুধু $w_i \le w$ হলে সম্ভব) — তাহলে বাকি ধারণক্ষমতা $w - w_i$ দিয়ে প্রথম $i-1$টি আইটেম থেকে সেরা মূল্য বের করতে হবে এবং তার সাথে $v_i$ যোগ করতে হবে, অর্থাৎ $v_i + dp[i-1][w-w_i]$।

অপটিমাল সাবস্ট্রাকচার আর্গুমেন্ট: ধরা যাক $dp[i][w]$-এর জন্য একটি অপটিমাল সমাধান $S$ আছে। যদি $S$-এ আইটেম $i$ না থাকে, তাহলে $S$ অবশ্যই প্রথম $i-1$টি আইটেম ও ধারণক্ষমতা $w$-এর জন্য একটি অপটিমাল সমাধান হতে হবে — কারণ যদি এর চেয়ে ভালো কোনো সমাধান $S'$ থাকত (প্রথম $i-1$টি আইটেম, ধারণক্ষমতা $w$-এ), তাহলে $S'$ নিজেই $S$-এর চেয়ে ভালো একটি সমাধান হতো মূল সমস্যাতেও — যা $S$-এর অপটিমাল হওয়ার সাথে সাংঘর্ষিক। একইভাবে, যদি $S$-এ আইটেম $i$ থাকে, তাহলে $S \setminus \{i\}$ অবশ্যই প্রথম $i-1$টি আইটেম ও ধারণক্ষমতা $w-w_i$-এর জন্য অপটিমাল হতে হবে (একই "কাট-অ্যান্ড-পেস্ট" যুক্তি)। দুই ক্ষেত্রেই অপটিমাল সমাধান ছোট সাবপ্রবলেমের অপটিমাল সমাধান থেকে গঠিত — এটাই অপটিমাল সাবস্ট্রাকচার। আর $dp[i-1][w]$-এর মতো অবস্থা বহু ভিন্ন $(i, w)$ থেকে পুনরায় প্রয়োজন হতে পারে — এটাই ওভারল্যাপিং সাবপ্রবলেম, যা L24-এর সাধারণ ব্যাখ্যার একটি সরাসরি প্রয়োগ।

৩ · যাচাই — নেইভ এক্সপোনেনশিয়াল ব্রুট-ফোর্স বনাম DP

উপরের রিকারেন্সটিকে কোনো cache ছাড়াই সরাসরি একটি রিকার্সিভ ফাংশন হিসেবে লিখলে সেটি একটি সঠিক কিন্তু $O(2^n)$ সময়ের ব্রুট-ফোর্স হয়ে যায় (প্রতিটি আইটেমে দুটি শাখা — নেওয়া অথবা না নেওয়া)। এটিই আমাদের "গ্রাউন্ড ট্রুথ" — এটি ধীর কিন্তু স্পষ্টভাবে সঠিক, কারণ এটি সংজ্ঞা থেকে সরাসরি সব সম্ভাবনা পরীক্ষা করে। নিচের কোডে এটি এবং ট্যাবুলেটেড DP পাশাপাশি চালিয়ে $n \le 15$ ও ছোট ধারণক্ষমতার একাধিক র‍্যান্ডম ইনস্ট্যান্সে তুলনা করা হয়েছে।

import random

def knapsack_brute(i, cap, weights, values, n):
    # নেইভ এক্সপোনেনশিয়াল রিকার্সন -- কোনো cache নেই, প্রতিটি আইটেমে দুটি শাখা
    if i == n or cap == 0:
        return 0
    if weights[i] > cap:
        return knapsack_brute(i + 1, cap, weights, values, n)
    skip = knapsack_brute(i + 1, cap, weights, values, n)
    take = values[i] + knapsack_brute(i + 1, cap - weights[i], weights, values, n)
    return max(skip, take)

def knapsack_dp(weights, values, capacity):
    # ট্যাবুলেটেড DP -- ঠিক একই রিকারেন্স, ইটারেটিভভাবে
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt = weights[i - 1]
        val = values[i - 1]
        for w in range(capacity + 1):
            if wt > w:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = max(dp[i - 1][w], val + dp[i - 1][w - wt])
    return dp[n][capacity]

rng = random.Random(42)
print(f"{'n':>3} | {'capacity':>8} | {'brute-force':>11} | {'DP':>6}")
for trial in range(8):
    n = rng.randint(3, 15)
    capacity = rng.randint(5, 30)
    weights = [rng.randint(1, 12) for _ in range(n)]
    values = [rng.randint(1, 20) for _ in range(n)]
    brute = knapsack_brute(0, capacity, weights, values, n)
    dp = knapsack_dp(weights, values, capacity)
    assert brute == dp, "মিসম্যাচ!"
    print(f"{n:>3} | {capacity:>8} | {brute:>11} | {dp:>6}")

print("\nসব ৮টি র‍্যান্ডম ইনস্ট্যান্সে brute-force == DP")