سلام دوستان مانشتی و CLRS دان لطفا به این سوال جواب بدید
نشان دهید که کوله پشتی کسری چگونه در زمان o(n حل میشود(با کد)؟
اصل مرتبه‌ی الگوریتم کوله پشتی کسری به خاطر مرتب سازیشه که n logn هست! منظورتون اینه که ایده‌ی دیگه ای وجود داره برای مسئله‌ی کوله پشتی که مرتبه n هست؟ بعیده: -? اگه منظورتون اینه یه hint بدید!
یه الگوریتمی توی فصل ۹ گفته که توی مرتبه‌ی n در یک مجموعه‌ی نا مرتب، عنصر وسط آن مجموعه را در حالت مرتب بودن میدهد.
فرض میکنیم یک مجموعه شامل عناصر vi/wi داریم.
بعد میدونیم که توی الگوریتم کوله پشتی کسری باید شروع کنیم تا جایی که میشه اونایی که vi/wi بزرگتری دارند رو برداریم، یعنی اگه به ترتیب نزولی مرتب شده باشند باید یه نقطه ای رو برای این که تا اون جا انتخابمون رو انجام بدیم پیدا میکنیم، و این کار رو بازگشتی انجام میدیم، یعنی اول عنصر وسط رو با همون الگوریتم مرتبه n فصل ۹ پیدا کنیم، بعد سه تا مجموعه درست کنیم، یکی اونایی که بیشتر از عنصر وسط هستند (A) یکی اونایی که مساوی عنصر وسط هستند (B) یکی هم اونایی که کمتر از عنصر وسط هستند © بعد بسته به این که مجموع عناصر بزرگتر از عنصر وسط یعنی مجموع اعضای مجموعه A چه مقداری داره دنبال اون نقطه‌ی شکست میگردیم. مثلا اگه مجموع اعضای A بیشتر از وزنی که کوله پشتی میتونه تحمل کنه بود، اون کاری رو که برای کل عناصر انجام دادیم برای عناصر مجموعه‌ی A انجام میدیم.
اما این الگوریتم هم به قیافه ش میاد که n logn باشه!
پ.ن: شرمنده! نتونستم بهتر از این توضیح بدم! حالم خوب نیست! همینم به زور نوشتم!
مرسی از توضیحاتت
چون در هربار مقایسه ۳ محموعه تشکیل شده با W: مثلا مجموعه ای که وزنش بیشتر از مقدار متوسط هست در مقایسه با W متوجه میشه که همه مجموعه رو باید بزاره و مقدار جایی رو هم که هنوز تو کوله باقی مونده با استفاده از الگوریتم بازگشتی از مجموعه دیگه برمیداره(در زمان n)و ۴ حالت رو به همین ترتیب مقایسه میکنه پس زمانش از مرتبه o(n)
توی هر مرحله عنصر وسط رو در مرتبه‌ی n پیدا میکنه و هر بار هم کل مجموعه رو ۲ یا ۳ قسمت میکنه انگار که n رو بر ۲ یا ۳ تقسیم کنه، پس میشه گفت به طور متوسط در logn مرحله به جواب میرسه با این استدلالی که من کردم مرتبه‌ی الگوریتم میشه n logn !
سلام
این الگوریتم از دو قسمت تشکیل شده:
الف)غیر بازگشتی:
۱) پیدا کردن میانه: از مرتبه‌ی n
۲) تشکیل سه مجموعه (اعضای کوچکتر از میانه)L و (اعضای مساوی با میانه) E و(اعضای بزرگتر از میانه) B: از مرتبه‌ی n
ب)بازگشتی:
۳) پر کردن کوله پشتی:
چون ما دنبال بیشترین‌ها هستیم میریم سراغ B :
۱) اگه مجموع اعضای B مساوی با w باشه، مسئله حله !
۲)اگه مجموع اعضای B بزرگتر ازw باشه، الگوریتم روی B تکرار میشه تا جایی که مجموع کوچکتر مساوی w بشه ؛ اگه مساوی شد میریم ۱ ؛ اگه کوجکتر شد میریم ۳ .
۳) اگه مجموع اعضای B کوچکتر ازw باشه ، کل B انتخاب میشه و کسری کوله از E و در صورت نیاز از L تامین میشه (با تکرار الگوریتم و مراحل ۱و۲و۳ روی E و در صورت نیاز L).
همون طور که دیدین در هر کدوم از این سه حالت الگوریتم روی n/2 اعضا تکرار میشه
بنابراین زمان بازگشتی برابر با: T(n)=T(n/2)+n
ودر نتیجه طبق master الگوریتم از مرتبه‌ی n هست.
(۲۰ آبان ۱۳۸۹ ۰۵:۲۹ ب.ظ)admin نوشته شده توسط: جالب شد قضیه، یعنی الگوریتمی از پیچیدگی n وجود داره برای این مسئله؟؟حب مسئله اینه که این الگوریتم اعضا رو مرتب نمیکنه بلکه هر بار یه مجموعه نامرتب از اعضای از میانه بیشتر تشکیل میده، جمعشون میکنه و اگه دید از w بزرگتر یا کوچکترن اصلاحشون میکنه تا به هدف برسه.
من هر طور فکر می کنم می بینم که این الگوریتم نیاز به یه مرتب سازی داره( به هر شیوه ای) و مرتب سازی رو با nlogn می شه انجام داد.
چون کوله پشتی کسری هست نمی شه از روش های hash استفاده کرد. جالب میشه دوستان این الگوریتم رو قرار بدن.( البته به صورت pdf و یا doc بهتره تا بشه خوندش)
(۱۹ آبان ۱۳۸۹ ۱۱:۵۲ ق.ظ)۵۴m4n3h نوشته شده توسط: توی هر مرحله عنصر وسط رو در مرتبه‌ی n پیدا میکنه و هر بار هم کل مجموعه رو ۲ یا ۳ قسمت میکنه انگار که n رو بر ۲ یا ۳ تقسیم کنه، پس میشه گفت به طور متوسط در logn مرحله به جواب میرسه با این استدلالی که من کردم مرتبه‌ی الگوریتم میشه n logn !
هر بار الگوریتم تنها روی نصف مجموعه تکرار میشه نه روی کل مجموعه به همین خاطر، T(n/2 داریم نه ۲T(n/2 .
سلام. خسته نباشید. من متوجه منظورتون از فصل ۹ و الگوریتمش نمیشم. اگه میشه یکم واسم توضیح بدین. من کتاب یا جزوه اون فصل ۹ ای که شما میگین رو ندارم. لطفا خود الگوریتم رو بگید. ممنون میشم
در کتاب طراحی الگوریتم پوران پژوهش فصل روشهای حریصانه توضیح الگوریتم امده است که با استفاده از میانه یابی با مرتبه n کوله پشتی کسری حل می شه