پاورپوینت درباره مسأله کوله پشتی

لینک دانلود و خرید پایین توضیحات

دسته بندی : پاورپوینت

نوع فایل :  .ppt ( قابل ویرایش و آماده پرینت )

تعداد اسلاید : 7 اسلاید

 قسمتی از متن .ppt : 

Backtracking

1

مسأله کوله پشتی 1-0 با روش backtracking

حل مسأله با استفاده از درخت فضای حالت

تا پایان جستجو امکان فهمیدن این که آیا یک گره جواب است یا خیر وجود ندارد.

باید بهینه سازی را درنظر داشت. اگر مجموع ارزش گره ها بیشتر از بهترین جوابی باشد که تا کنون به دست آورده ایم, مقدار بهترین جواب را به مقدار جدید تغییر می دهیم.

فرض: weight: مجموع وزن کالاهایی که تاکنون به گره ای اضافه شده اند.

profit : مجموع ارزش کالاهایی که تا گرعه جاری به حساب آمده اند.

bound: یک حد بالا برای ارزشی که می توانیم با بسط گره به آن برسیم.

totweight: حداکثر وزن کالاهای قابل انتخاب

maxprofit: مقدار ارزش بهترین جوابی که تا کنون پیدا شده.

Backtracking

2

کالاها را به صورت غیرنزولی بر اساس مقادیر pi / wi مرتب می کنیم.

گره سطح k : گرهی که موجب تجاوز مجموع وزن از مرز M می شود.

در سطح i پیش بینی از حداکثر ارزش قابل دستیابی, برابر با مجموع ارزش به دست آمده به علاوه ارزش کالاهای باقی مانده تا سطح k-1 به علاوه مقدار قابل انتخاب از کالای k ام (با فرض این که بتوان بخشی از آن را انتخاب کرد) می باشد.

bound ≤ maxprofit : گره غیر وعده گاه است.

totweight = weight+  wj

bound = (profit+  pj )+(M-totweight)(pk / wk)

j=i+1

k-1

j=i+1

k-1

ارزش اولین k-1

کالای انتخاب شده

ظرفیت باقی مانده

برای کالای k ام

ارزش واحد وزن

کالای k ام

Backtracking

3

مثال

profit

weight

bound

هر گره

M=16

Backtracking

4

0

0

115

0

40

2

115

1

40,2