در مسئلهٔ کوله‌پشتیِ صفر و یک، هر قلم را یا کامل انتخاب می‌کنیم یا کنار می‌گذاریم؛ تکرار یا برداشتن بخشی از قلم مجاز نیست. هدف، بیشترین ارزشِ مجموع زیر سقف ظرفیت است. نسبتِ ارزش به اندازه می‌تواند راهنمای شهودی باشد، اما در این مدل جواب بهینه را تضمین نمی‌کند. مثالِ سه‌قلمیِ این صفحه هم انتخاب‌ها را بازسازی می‌کند و هم یک خطای رایجِ کدِ یک‌ردیفی را نشان می‌دهد.
سه قلم و ظرفیت۷
داده‌ها کاملاً ساختگی‌اند. هر قلم یک‌بار موجود است؛ اندازه و ارزش صحیح‌اند و ارتباطی با قیمت خدمات اپرا یا ظرفیت واقعی تیم ندارند.
| قلمِ صفرمبنا | اندازه | ارزش | نسبت ارزش به اندازه |
|---|---|---|---|
| ۰ | ۲ | ۵ | ۲٫۵ |
| ۱ | ۳ | ۷ | ۷÷۳ |
| ۲ | ۴ | ۹ | ۲٫۲۵ |
روشِ نسبت‌محور، اول قلم۰ و سپس قلم۱ را جا می‌دهد؛ اندازهٔ۵ و ارزش۱۲ دارد و ظرفیتِ باقیماندهٔ۲ برای قلم۲ کافی نیست. اما انتخاب قلم‌های۱ و۲ دقیقاً ظرفیت۷ را پر می‌کند و ارزش۱۶ دارد. این اختلاف از تقسیم‌ناپذیری می‌آید؛ حکم مسئلهٔ کوله‌پشتیِ کسری را به صفر و یک منتقل نکنید.
جدول باید ظرفیتِ باقیمانده را هم بشناسد
dp[i][c] در فایل ما بهترین ارزش با استفاده از i قلمِ اول و سقف ظرفیت c است. برای قلمِ تازه با اندازهٔw و ارزشv، دو حالت داریم: حذف آن و گرفتن مقدار ردیف قبل، یا انتخاب آن و افزودن v به بهترین جوابِ ردیف قبل با ظرفیت c−w. حالت دوم فقط وقتی w≤c مجاز است.
exclude = dp[i-1][c] include = value + dp[i-1][c-size] # only if size <= c dp[i][c] = max(exclude, include)
هر دو شاخه از ردیف قبل می‌خوانند تا قلم تازه دوباره مصرف نشود. ردیف صفر و ستونِ ظرفیت صفر مقدار۰ دارند. آخرین خانهٔ جدول برای سه قلم و ظرفیت۷ برابر۱۶ است؛ جدولِ کاملِ چهار ردیف و هشت ستون در JSON وجود دارد. فقط نگه‌داشتن «بهترین ارزش پس از هر قلم»، بدون ظرفیت، اطلاعات لازم را از دست می‌دهد.
از عدد۱۶ به خودِ اقلام برگردیم
از ردیف آخر و ظرفیت۷ رو به عقب می‌رویم. اگر مقدار نسبت به ردیف قبل بیشتر شده، آن قلم انتخاب شده و اندازه‌اش از ظرفیت کسر می‌شود؛ در تساوی، قراردادِ فایل شاخهٔ حذف را نگه می‌دارد. خروجی، اقلامِ صفرمبنای [۱،۲] با اندازهٔ کل۷ و ارزش۱۶ است. کد جدا کنترل می‌کند قلم تکراری نباشد، اندازه از سقف نگذرد و جمع ارزشِ انتخاب‌ها با عدد جدول برابر باشد.
برای کنترل مستقل، همهٔ هشت زیرمجموعهٔ سه قلم را می‌سازیم؛ هر کدام اندازه، ارزش و برچسبِ مجازبودن زیر سقف دارد. بیشترین ارزش میان زیرمجموعه‌های مجاز۱۶ است. این بررسیِ کوچک، شاهدِ درست‌بودن خروجی همین مثال است؛ روش فهرست‌کردنِ همهٔ زیرمجموعه‌ها برای تعداد زیاد اقلام مناسب نیست.
حلقهٔ صعودی چه چیزی را خراب می‌کند؟
یک قلمِ جدا با اندازه۲ و ارزش۵ و ظرفیت۴ بگیرید. اگر جدول را یک‌ردیفی کنیم و ظرفیت را از۲ به۴ بالا ببریم، خانهٔ۴ از خانهٔ۲ای می‌خواند که همین دور با همان قلم تازه۵ شده است؛ نتیجه۱۰ یعنی دو بار مصرفِ یک قلم. کد این خطا را واقعاً اجرا کرده است، نه اینکه فقط درباره‌اش هشدار بدهد.
برای همین به‌روزرسانیِ یک‌ردیفیِ صفر و یک، حرکتِ ظرفیت از بزرگ به کوچک مانعِ خواندنِ نسخهٔ تازهٔ همان دور می‌شود و جواب۵ می‌ماند. جدولِ اصلیِ دو‌بعدی ما از ابتدا ردیفِ قبلیِ ثابت دارد. ترتیبِ اجرای یک حلقه می‌تواند قراردادِ «یک بار» را به قراردادِ «تکرار» عوض کند؛ نتیجه۱۰ در مدلِ تکرارپذیر شاید مجاز باشد، اما جواب مسئلهٔ این صفحه نیست.
اندازهٔ ورودی و مرز کاربرد
برای n قلم و ظرفیتِ صحیح C، این جدول حدود n×C خانه را پردازش می‌کند. چون C خودش یک عدد در ورودی است و تعداد بیت‌های نوشتنش بسیار کمتر از C می‌تواند باشد، این روش را شبه‌چندجمله‌ای می‌نامند؛ «همیشه سریع روی هر ظرفیت بزرگ» نتیجه نمی‌شود. فایل برای تمرین، حداکثر۱۲ قلم و ظرفیت۱۰۰ را می‌پذیرد؛ اندازهٔ صفر، ارزش منفی و ظرفیت اعشاری هم واقعاً رد شده‌اند.
این یک مسئلهٔ تصمیم‌گیریِ محدود با دادهٔ معلوم است و یادگیری از تجربه انجام نمی‌دهد. Value Iteration با مدل احتمالی ارزشِ وضعیت‌های یک فرایند چندگامی را حساب می‌کند؛ تخصیص یک‌به‌یک هم قید متفاوتی دارد. برای کاربرد پاسخ‌گویی یا پیگیری در کسب‌وکار، نیاز را در مسیر راهکارهای اپرا مشخص کنید؛ این مثال بهینه‌ساز داخلی محصول یا نتیجهٔ واقعی مشتری نیست.
فایل تمرین و منبع
کد کامل Python؛ بازتولید محاسبه و کنترل مستقل · دادهٔ آموزشی، مراحل محاسبه و نتیجهٔ کنترل مستقل
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.