site2017

تعریف سوال
شما یک کوله پشتی دارید که حجم ثابتی دارد. همچنین تعدادی وسیله نیز دارید که حجم هر کدام را به شما داده اند. می‌خواهید تعدادی از این وسیله‌ها را در کوله پشتی بریزید به طوری که بیشترین حجم ممکن از کوله پشتی اشغال شود. (فرض کنید شکل وسایل طوری است که فضای بی‌استفاده بین آن‌ها باقی نمی‌ماند.)

الگوریتم
این مسئله یکی از پایه‌ای‌ترین مسائل برنامه‌ریزی پویا است و صورت‌های مختلفی دارد که در انتها به آن‌ها و ایده‌ی اثبات‌شان اشاره می‌شود.
برای حل مدل ساده‌ی سوال، یک آرایه دوبعدی به نام dd به ابعاد(n+1)×(W+1)(n+1)×(W+1) را در نظر بگیرید که در آن nn تعداد وسایل مختلفی که می‌توانیم در کوله‌پشتی بگذاریم وWW حجم کوله‌پشتی است.
مقدارdi,jdi,j برابر یک است اگر و تنها اگر بتوان فقط با استفاده از ii وسیله‌ی اول، دقیقا حجم jj از کوله‌پشتی را پر کرد. یعنی یک زیرمجموعه‌ از ii عضو اول وجود دارد که مجموع وزن‌شان jj است. در غیر اینصورت، مقدارش برابر صفر است.
جواب مسئله بزرگترین اندیس jj است که dn,jdn,j برابر یک باشد.
مقداردهی اولیه: با استفاده از ۰۰ وسیله‌ی اول (استفاده نکردن از وسایل) فقط می‌توان حجم ۰۰ را تولید کرد (کوله‌پشتی خالی) پس تمام خانه‌های به صورت d0,jd0,j برابر صفر اند به جز d0,0d0,0 که برابر ۱۱ است.
به روز رسانی: برای به دست آوردن di,jdi,j دو حالت وجود دارد این که خود وسیله‌ی ii ام در کوله‌پشتی نباشد که در این صورت باید برای این که مقدار یک شود، مقدار di−1,jdi−1,j برابر ۱۱ باشد. حالت دیگر این است که خود وسیله در کوله پشتی باشد. پس در این حالت مقدار در صورتی یک می‌شود که (مقدار حجم وسیله‌ی ii ام را aiai بگیریم) di−۱,j−aidi−۱,j−ai با فرض j≥aij≥ai برابر یک باشد.
شبه کد:

d = {0}
d[0][0] = 1

for i from 1 to n
for j from 0 to W
d[i][j] = d[i-1][j]
if j >= a[i] and d[i-1][j-a[i]] == 1
d[i][j] = 1
اگر دقت کنید می‌بینید احتیاج خاصی به نگه داشتن یک آرایه‌ی دوبعدی نداریم چون برای محاسبه‌ی هر ستون، فقط به ستون قبلی احتیاج داریم و فقط باید ۲ ستون را نگه‌داریم. اما حتی می‌توانیم از این هم جلوتر برویم و فقط یک ستون داشته باشیم. اما در اینجا باید حواس‌مان باشد که اشتباه زیر را انجام ندهیم.
شبه کد با آرایه‌ی یک بعدی (اشتباه):

d = {0}
d[0] = 1

for i from 1 to n
for j from 0 to W
if j >= a[i] and d[j-a[i]] == 1
d[j] = 1
کد بالا یک مشکل دارد. به نظرتان مشکلش چیست؟
فرض کنید در فقط یک وسیله داریم مثلا با حجم ۲ واحد و حجم کوله‌پشتی برابر ۴ است. پس فقط می‌توان ۲ واحد از کوله‌پشتی را پر کرد. اما اگر شبه کد بالا را برای آن اجرا کنید، می‌بینید که مقدار d4d4 برابر یک است. چون با استفاده از وسیله‌ی اول که حجم دو واحد داشت، مقدار d2d2 را یک کردیم، اما بعد از این متوقف نشدیم بلکه چون مقدار d2d2 برابر یک بود، مقدار d4d4 را نیز برابر یک قرار دادیم. پس انگار بیش از یک وسیله با حجم دو داشتیم. در واقع این کد جواب مسئله‌ی دیگری به نام خرد کردن پول است که در آن به تعداد نامتناهی از هر کدام از وسایل داریم.
حال بیایید سعی کنیم مشکل کد بالا را حل کنیم. مشکل این بود که اول با استفاده از وسیله‌ی اول (یا بقیه‌ی وسایل) مقدار خانه‌های پایین جدول را به روز رسانی کردیم و سپس دوباره با استفاده از همان وسیله، مقادیر خانه‌های بالاتر را نیز به روز رسانی کردیم. چطور می‌شود اگر خانه‌ها را به ترتیب دیگری پیمایش کنیم تا این مشکل پیش نیاید؟ حجم وسایل که نمی‌تواند منفی باشد. پس اگر بالا به پایین آرایه را به روز رسانی کنیم، این مشکل پیش نمی‌آید. خودتان هم کمی فکر کنید که چرا این روش درست است.
بر همین اساس کد را تغییر می‌دهیم. شبه کد با آرایه‌ی یک بعدی (درست):

d = {0}
d[0] = 1

for i from 1 to n
for j from W to 0
if j >= a[i] and d[j-a[i]]
d[j] = 1
پیچیدگی‌ الگوریتم
پیچیدگی زمانی که در تمام حالت‌ها از O(n×W)O(n×W) است. مقدار حافظه‌ی مورد نیاز نیز O(W)O(W) است.

ساخت سايت