سلام دوباره . از اونجایی که بجث برنامه نویسی پویا خیلی مهم و نسبتا سخت تره ، نیاز به وقت بیشتری داره.
(مسابقه به گروه اضافه شد . البته سوالا صرفا مربوط به dp دو بعدی نیست )
بذارین مثال معروف کوله پشتی 0 و 1 رو این بار با هم چک کنیم :
( این مسئله یکی از پراستفاده ترین مسئله هایی که میشه با یاد گرفتنش برای سوالای دوبعدی پویا راحت تر ایده پیدا کرد )
- مسئله میگه آیا میشه یه کوله پشتی به وزن w رو با وزنه های به وزن m1,m2,...mn کامل پر کنیم یا نه ؟
برای جواب دادن به این سوال... نمیتونیم به صورت حریصانه عمل کنیم ، یعنی مثلا بگیم اول بزرگترین وزنه رو بذارم بعد باقیمونده رو با بقیه پر کنم یا هر ایده ی مشابه این .
اما میشه تمام حالت های ممکن انتخاب وزنه هارو چک کرد که بطور حتم جواب پیدا میشه و چون ما n تا عنصر تو مجموعه ی وزنه هامون داریم ، باید تمام زیرمجموعه های ممکن یعنی 2 بتوان n حالت رو چک کنیم ! ولی زمان پاسخ دهی این روش ماکزیمم تا حدودا 20 میتونه قابل تحمل باشه. ( 2^20 = 1048576 حالت )
همونطور که میدونید برای درست کردن زیرمجموعه ها برای هر عضو دوحالت امکان داره : یا تو زیرمجموعمون هست یا نیست . پس کد این روش بصورت بازگشتی خیلی سادست و برای برنامه نویس راحته ولی برای کامپیوتر واقعا زمان بره :
bool knapsack(int w , int n)
{
if ( w == 0 ) return true; // knapsack is full
if ( w<0 || n<1 ) return false; // overflow , out of weight
return knapsack(w , n-1) || knapsack(w-a[n] , n-1); // IgnoreThis or ChooseThis
}
اما چون اینجا زیرمسئله های تکراری داریم میتونیم با استفاده از روش بیاد سپاری که تو پست قبل هم بود سرعت اجرای برنامه رو بهبود بدیم :
int ks[MAX][MAX]; // all members = -1 -> -1:not calculated , 0:false , 1:true
bool knapsack(int w , int n)
{
if (ks[n][w] != -1) return ks[n][w]; // memorized
if ( w == 0 ) return true; // knapsack is full
if ( w<0 || n<1 ) return false; // overflow , out of weight
ks[n][w] = knapsack(w , n-1) || knapsack(w-a[n] , n-1); // IgnoreThis or ChooseThis
return ks[n][w];
}
... روش پویا با جدول بندی اضافه خواهد شد ...
اگه برنامه نویسی بلد بودی وبلاگ نداشتی *** ** ....سایت داشتی