dadvand
عضو جدید
به مسئله زیر دقت کنید . پیشاپیش بگم هر کی بتونه برنامه ای برای این مسئله بنویسه 1 میلیون دلار از موسسه ریاضی claymath میگیره و توی CNN هم ازش برا مصاحبه دعوت میکنند . 1 میلیون از دانشگاه هاروارد میگیره . و اینها فقط شروعش است و خیلی دانشگاهها (MIT ,... )واسش جایزه گذاشتن .
البته نه برای این مسئله بلکه برای چند مسئله از این خانواده . ولی چون اثبات میشه که هر کدام از آنها حل شود بقیه هم حل شده هسنتد پس یکیش کافی است . در ضمن حتی اگر ثابت کنید که برایش حلی وجود ندارد باز جایزه را برده اید .
مسئله کوله پشتی :
دزدی به خانه ای میرود و یک کوله پشتی به گنجایش W همراهش است . در آن خانه اجناسی با وزن w(i) و ارزش k(i) وجود دارد . هدف انتخاب اجناسی است که بیشترین سود نصیب دزد شود .
مثال W=10
w1=5 t1=10
w2=2 t1 =2
w3=3 t3=5
w4=9 t4=15
w5=8 t5 =16
جواب : w2,w5
مثال 2:
W=16
w1=2 t1=40
w2=5 t2=30
w3=10 t3=50
w4=5 t4=10
جواب : w1,w3
خوب هدف نوشتن برنامه ایست که این رو با پیچیدیگی زمانی چند جمله ای حل کند. خوب چون اعتقاد ندارم که این سوال منحصر به بچه های الگوریتم پاس کرده باشه و بنظرم همه باید درموردش فکر کنند و البته الگوریتم پاس کرده و نکرده احتمالا در این مورد با هم فرقی ندارند biggrin یک راهمنایی برای اصطلاح پیچیدگی چند جمله ای الگوریتم میکنم .
1: برنامتون باید تعداد حلقه تودرتو یا غیر تودرتو متناهی داشته باشه (هر چه قدر اشکال نداره فقط متناهی یعنی اگه از 10000 حلقه for استفاده مکنین باز اشکال نداره فقط متناهی باشه). 2
: تعداد loop حلقه ها متناهی باشه یعنی تعداد باری که اجرا میشوند متنهاهی باشه یعنی مدام در هر loop رنج آن اضافه نشه .
3: اگر از الگوریتم بازگشتی استفاده میکنید در حلقه بازگشتی بیش از یکبار تابع صدا زده نشود .
خوب چون احتمال میره کمتر کسی در سایت بتونه حلش کنه و در نتیجه پست کمتری نوشته میشه و در نتیجه تاپیک به آخرای لیست فرستاده میشه پس هر چی دلتون میخواد بنویسین که لااقل پست در اول لیست باقی بمونه و همه ببینن ، شاید یکی بتونه حلش کنه .
اولین نظر رو خودم مینویسم : چون حل این مسئله طبق قانون ، شراکت در اعمال جرم دزدی است پس من از ارائه راحلی که پیدا کردم صرف نظر میکنم و آن جایزه ها رو فقط تله ای برای شناسایی مجرمین و دزدان میدونم و از خیرش گذشتم .
ولی خوب جدای از شوخی میلیونها سیب هروز از درخت می افنتد پایین ولی فقط یکی به این افتادن دقت کرد .
البته نه برای این مسئله بلکه برای چند مسئله از این خانواده . ولی چون اثبات میشه که هر کدام از آنها حل شود بقیه هم حل شده هسنتد پس یکیش کافی است . در ضمن حتی اگر ثابت کنید که برایش حلی وجود ندارد باز جایزه را برده اید .
مسئله کوله پشتی :
دزدی به خانه ای میرود و یک کوله پشتی به گنجایش W همراهش است . در آن خانه اجناسی با وزن w(i) و ارزش k(i) وجود دارد . هدف انتخاب اجناسی است که بیشترین سود نصیب دزد شود .
مثال W=10
w1=5 t1=10
w2=2 t1 =2
w3=3 t3=5
w4=9 t4=15
w5=8 t5 =16
جواب : w2,w5
مثال 2:
W=16
w1=2 t1=40
w2=5 t2=30
w3=10 t3=50
w4=5 t4=10
جواب : w1,w3
خوب هدف نوشتن برنامه ایست که این رو با پیچیدیگی زمانی چند جمله ای حل کند. خوب چون اعتقاد ندارم که این سوال منحصر به بچه های الگوریتم پاس کرده باشه و بنظرم همه باید درموردش فکر کنند و البته الگوریتم پاس کرده و نکرده احتمالا در این مورد با هم فرقی ندارند biggrin یک راهمنایی برای اصطلاح پیچیدگی چند جمله ای الگوریتم میکنم .
1: برنامتون باید تعداد حلقه تودرتو یا غیر تودرتو متناهی داشته باشه (هر چه قدر اشکال نداره فقط متناهی یعنی اگه از 10000 حلقه for استفاده مکنین باز اشکال نداره فقط متناهی باشه). 2
: تعداد loop حلقه ها متناهی باشه یعنی تعداد باری که اجرا میشوند متنهاهی باشه یعنی مدام در هر loop رنج آن اضافه نشه .
3: اگر از الگوریتم بازگشتی استفاده میکنید در حلقه بازگشتی بیش از یکبار تابع صدا زده نشود .
خوب چون احتمال میره کمتر کسی در سایت بتونه حلش کنه و در نتیجه پست کمتری نوشته میشه و در نتیجه تاپیک به آخرای لیست فرستاده میشه پس هر چی دلتون میخواد بنویسین که لااقل پست در اول لیست باقی بمونه و همه ببینن ، شاید یکی بتونه حلش کنه .
اولین نظر رو خودم مینویسم : چون حل این مسئله طبق قانون ، شراکت در اعمال جرم دزدی است پس من از ارائه راحلی که پیدا کردم صرف نظر میکنم و آن جایزه ها رو فقط تله ای برای شناسایی مجرمین و دزدان میدونم و از خیرش گذشتم .
ولی خوب جدای از شوخی میلیونها سیب هروز از درخت می افنتد پایین ولی فقط یکی به این افتادن دقت کرد .