صفحه 1:
Pelee oven
صفحه 2:
A
BP ne PE ا Cre CULE RE Cpe e SE ery
بهينه سازى تركيباتى است. فرض كنيد مجموعه اى از اشياءكه هر كدام داراى وزن و ارزش
الل ا اال ا ال ا الل و م
انتهاب شده كوجكتر يا مساورى حدى از بيش تعيين شده»وارزش لن ها بيشينه شود. علت
نامكذارى اين مسئله»جهانكردى است كه كوله يشتى اى با اندازه محدود دارد و بايد آن را با مفيد
ترین صورت ممکن از اشیا پر کند. معمولا در تخصیص منابع با محدودیت های مالی,با اين
مسئله رویرو هستیم.
همجنين مسائلى از اين قبيب در تركيبات» نظريه ييجيدكى محاسباتى:رمزنكارى و رياضيات
كاربردى به جشم ميخورد
صفحه 3:
تاریخچه
مسئلة كوله بشتى بيش از يك قرن مورد مطالعه قرار كرفته و اولين بررسى در سال 18917 انجام
كرفتهاست. هر جند اولين دادهدهاى ثبت شده در اين موردء به كارهاى رياضيدانى به نام (6©2 © 06
ی 50-00-05
وجود داشتهاست.
fe OI ال ل ا ل ا Seucer)
3
در سال »١388 تحقيقى از دانشكاه استونى بروك بر روى مجموعهداى از الكوريتمهاء نشان داد كه از
میان ۷۵ مسئله الگوریتمی» مسئله کوله پشتی؛ ۱۸ امین مسئله معروف و ۴ امین مسئله پرکاربرد بعد از
۱ i arc ee Re ee eS eC)
صفحه 4:
2k Sues ity al Salis ا اد سا
از بين وسائل كوناكونى كه بيشترين راحتى را برايش فراهم مىسازند ير كند. اين مسئله مىتواند با
شماره‌گذاری این وسائل از 4 تا ب و تعریف برداری از متغیرهای دو دوی به صروت ریاضی فرمول
00010009 0 0000 اس oo = ا FOREMAN
وسيله : ام فراهم مىآورد و وزن لن و 7 اندازه كوله يشتى باشد. مسئله ما انتخاب بردارى از بين
ا ا ا 2 000
012 مسائلی که می‌توانند به 5
صفحه 5:
ادامه _ تعریف 6
در اين رابطه بايد روشى براى حل اين مسئله بيدا كرد. يك روش ابتدايى كه در نكاه اول
توجه ما را به خود جلب مىكندء عبارت از برنامهنويسى براى كامبيوتر به منظور امتحان
كردن تمامى بردارهاى دودويى ممكن د استء تا از بين بردارهايى كه محدوديت مسئله
را ارضاء می‌کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است.
صفحه 6:
ادامه تعریف
بطورىكه يك كامييوتر فرضى كه مىتواند يك بيليون بردار را در يك ثانيه امتحان كند؛
براى - 2٠» بيش از "٠ سال وقت لازم دارد و بيش از ۰ سال برای < ۶۱ و ده‌ها
قرن براى - ه 2ج والى آخر. با اين وجودء با استفاده از الكوريتمهايى خاص مىتوان در
بسيارى موارد مسئلداى با - (0000000000 © را در عرض جند ثانيه روى يك
۹ |
صفحه 7:
ادامه_تعریف6
SLL eer و
و را = PR ees og
آخر. با اين وجودء با استفاده از الكوريتمهايى خاص مئتوان در بسيارى موارد مسئلهاى با < -
2000 را در عرض جند ثانيه روى يك كامبيوتركوجك حل كرد.
معروف‌ترین نوع از اين مسنله» مسئله كوله يشتى ٠ و ١ استث. يعنى تعداد از هر شىء يا ٠ است (آن
شی را انتخاب نمی‌کنیم) یا ۱ (آن شی انتخاب می‌شود).
صفحه 8:
پیچیدگی محاسباتی
از ديد علوم كامبيوتر» مسئله كوله يشتى شايان توجه است زيرا:
* الگوریتمی با زمان اجرای شبه چند جمله ای با استفاده از برنامه نویسی پویا دارد.
۶ الگوریتمی تقریبی با زمان چند جمله ای دارد که از الگوریتم های زمان شبه چند جمله ای به عنوان
یک زیر برنامه استفاده کند.
« حل دقیق این مسئله ای از نو -باسبن(-۳() است؛ بنابراین پیش بینی شده که راه حلی که هم
درست هم سريع باشد با زمان اجراى جند جمله اى براى هر ورودى دلخواه ؛ ندارد.
صفحه 9:
کاربرد ها
مسئله كوله يشتى مىتواند در تصميمكيرىهايى كه در دنياى واقعى با آنها روبرو هستيم؛»
مورد استفاده قرار كيرد. مانند بريدن كالا بمطورىكه كمترين مقدار به هدر رودء انتخاب
سرمايهكذارىها و سبد سهام؛ انتخاب دارايىها براى مسئله امنيت دارايىهاى قبليو ساختن
کلیدها برای سیستم رمزنگاری کوله پشتي مرکل-هلمن.
صفحه 10:
laa ps DSS ۰۳۱
يكى از كاربردهاى اوليه مسئله كوله يشتى» طراحى و بارم بندى آزمون است به نحوى كه آزمون دهنده
ا 5200
خواهد شد. براى مثال؛ اكر آزمون داراى ©) سؤال» هر سؤال به ارزش (00 نمره باشدء آزمون دهنده
ينه نمره ممكن. 00000 برسد. اما براى آزمونهايى با بارم بندى
ا ا ا ل ا 6 ا ا ا ا
بايد فقط (0) سؤال را ياسخ دهد تا به
آموزان با آزمونى با بارم بندى ناهمكنء با جمع بارم ©©0 روبرو هستند. از دائش آموزان خواسته
ا ا ل ا ا ا ل 6622
زير مجموعههايى؛ جمع نمرداى برابر با 00000 خواهند داشت؟ براى هر دانش آموزء ياسخ كويى به كدام
زير مجموعه از سؤالات» نمره بيشترى را به ارمغان مىآورد؟
صفحه 11:
a | ری کچ
نمونه‌ای از مسئله کوله پشتی یک بعدی: چه جعبه‌هایی باید
انتخاب شوند تا مقدار يول بيشينه شود اما وزن جعبههاى
مذكور بيشتر از ١5 كيلوكرم نشود؟ يك مسئله جند محدوديتى»
مىتواند هم وزن و هم حجم جعبهها را در نظر بكيرد.
مدل‌سازی اندازه و شکل جعبهها» یک مسئله بسته‌بندی است.
5
9 2
3
9
ENS wee Nea re ا we IOS B))
ار
شکل باشد. یعنی از هر جعبه فقط یکی داشته باشیم» تمامی
(ee ا
3
صفحه 12:
Cae 47 5
الكوريتم تقريبى حريصانه
عمه() عرسسی9) الگوریتمی نقریبی از نوع حریصانه برای حل مسئله کوله پشتی بیکران ارائه داد.
به اين ترتيب كه اشيا را به ترتيب نزولى بر حسب ارزش به واحد وزن مرتب مىكندءسيس از شى شماره
oreo ey ۱
ای برای آن نوع باقی نماند. آنگاه سراخ شی بعدی می‌رود.
(دقت کنید که در اين نسخه از سوال؛ محدودیتی برای تعداد اشیا نداریم)
صفحه 13:
۲
مسئله کوله پشتی بیکران؛ هیچ محدودیتی روی تعداد اشیا قاثل نمی‌شود. یعنی از هر شی, به هر تعداد
دلخواهى مىتوان انتخاب كرد. نسخداى ازين سؤال كه بيش از همه مورد توجه قرار مىكيردء داراى
eS) ۳
یک مسئله تصمی (ul
Ewe
۶ برای هر شی» وزن و ارزش آن برابرند.
صفحه 14:
8 مسئله كوله يشتى بى كران
200120 2 ا ا 0 ا اا ا 2 NSRP CN ESS
با استفاده از برنامهنويسى يويا قابل حل است. بيشترين ارزش قابل دستيابى از مجموعه
a) eS
صفحه 15:
روابط پوشانندگی در مسئله کوله پشتی بیکران
ا سا ار
مىتوان مسئله را سادهتر كرد. براى مثال» فرض كنيد براى شى اى مانند ؛» مىتوان زير مجموعه از
اشيا به نام يافت طورىكه ارزش مجموع آنها بزركتر از ارزش إو وزن مجموع آنها كمتر از وزن
ا ا ا ا ا ل ال 2 0
بيدا كردن روابط يوشانندكى؛ به ما كمك مىكند تا تا حجم فضاى جستجو را در حد قابل توجهى
کاهش دهیم. انواع مختلفی از روابط پوشانندگی وجود دارند»
صفحه 16:
BB ever nant
Rea eee epee ee ا ere eet ee
rere ress Phy ee wee aT OL te Re eee
پوشانندگی چندگانه : شی ؛ ام ۰ به طور چندگانه توسط شی ز پوشانده شده است. <
< پوشانندگی ماژولار : شی : ام » به طور ماژولار توسط شی ز پوشانده شده است.
صفحه 17:
کوله‌پشتی ۰ و ۱
اين مسئله يك مسئله در زمينه بهينهسازى تركيبياتى مى باشد.در اين مسئله تعدادى شىء با وزن و ارزش
مشخص داده می‌شود. یکی دیگر از اطلاعات اين مسئله تعداد مورد نیاز هر شیء است که با توجّه به این
تعداد و با در نظر گرفتن بیشترین ارزش باید از میان اشیا ء مورد نظر گردایه ای انتخاب شود.
اين مسئله مانند اين است كه در نظر بكيريم دزدى به مغازه اى رفته و وزن بيشترين بارى كه مىتوائد
بدزدد رى ميباشد. در اين ميان - شى وجود دارد كه وزن هركدام ؛ بن و ارزش هركدام ؛ ميباشد
صفحه 18:
راه حل كولهيشتى ٠ و ١
راه حل اول حل اين مسئله به صورت مستقيم است به اين صورت كه:
1. از آن جايى كه > شى داريم يس در مجموع © به توان > تركيب ممكنه از اشيا داريم
”. همه تركيب هارا بررسى ميكنيم و تركيب با بيشترين ارزش و با وزن كمتر يا مساوى (1) را انتخاب
۱ ال ا madd