مسئله کوله‌پشتی
Knapsack Problemدر 0/1 Knapsack هر آیتم weight و value دارد و حداکثر یک بار انتخاب می‌شود. هدف بیشینه کردن value بدون عبور از ظرفیت است.
اول این مفهوم را در ذهن نگه دار
در 0/1 Knapsack هر آیتم weight و value دارد و حداکثر یک بار انتخاب می‌شود. هدف بیشینه کردن value بدون عبور از ظرفیت است.
چطور کار می‌کند؟ ساده و مرحله‌ای
State رایج DP بهترین value با استفاده از i آیتم اول و ظرفیت c است.
برای هر آیتم بین نگرفتن و گرفتن آن در صورت جا شدن مقایسه می‌کنیم.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
State را دقیق تعریف کن.
Transition یا choice را از stateهای کوچک‌تر بنویس.
Base Case را مشخص و بعد بین memoization، tabulation یا backtracking انتخاب کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مسئله کوله‌پشتی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function knapsack(items, capacity) {
const dp = Array(capacity + 1).fill(0);
for (const { weight, value } of items) {
for (let c = capacity; c >= weight; c--) {
dp[c] = Math.max(dp[c], dp[c - weight] + value);
}
}
return dp[capacity];
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(nW) DP
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی زیرمسئله‌ها overlap دارند و جواب از stateهای کوچک‌تر ساخته می‌شود DP مناسب است.
کجا معمولاً اشتباه می‌کنیم؟
- قبل از تعریف state سراغ recurrence نرو.
- DPای نساز که state space آن از خود مسئله بزرگ‌تر و غیرعملی باشد.
مدل یک پاسخ حرفه‌ای
اول variant را مشخص کن: 0/1، Unbounded یا Fractional. الگوریتم درست برای این‌ها متفاوت است.
مسئله کوله‌پشتی چه مسئله‌ای را حل می‌کند؟
در 0/1 Knapsack هر آیتم weight و value دارد و حداکثر یک بار انتخاب می‌شود. هدف بیشینه کردن value بدون عبور از ظرفیت است.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(nW) DP است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
قبل از تعریف state سراغ recurrence نرو.