اگر طالب چند میلیون دلار هستین این مسئله کوچیک رو حل کنین.

dadvand

dadvand

عضو جدید
به مسئله زیر دقت کنید . پیشاپیش بگم هر کی بتونه برنامه ای برای این مسئله بنویسه 1 میلیون دلار از موسسه ریاضی claymath میگیره و توی CNN هم ازش برا مصاحبه دعوت میکنند . 1 میلیون از دانشگاه هاروارد میگیره . و اینها فقط شروعش است و خیلی دانشگاهها (MIT ,... )واسش جایزه گذاشتن :eek::).
البته نه برای این مسئله بلکه برای چند مسئله از این خانواده . ولی چون اثبات میشه که هر کدام از آنها حل شود بقیه هم حل شده هسنتد پس یکیش کافی است . در ضمن حتی اگر ثابت کنید که برایش حلی وجود ندارد باز جایزه را برده اید .
مسئله کوله پشتی :
دزدی به خانه ای میرود و یک کوله پشتی به گنجایش 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: اگر از الگوریتم بازگشتی استفاده میکنید در حلقه بازگشتی بیش از یکبار تابع صدا زده نشود .
خوب چون احتمال میره کمتر کسی در سایت بتونه حلش کنه و در نتیجه پست کمتری نوشته میشه و در نتیجه تاپیک به آخرای لیست فرستاده میشه:razz: پس هر چی دلتون میخواد بنویسین که لااقل پست در اول لیست باقی بمونه و همه ببینن ، شاید یکی بتونه حلش کنه :D.
اولین نظر رو خودم مینویسم : چون حل این مسئله طبق قانون ، شراکت در اعمال جرم دزدی است پس من از ارائه راحلی که پیدا کردم صرف نظر میکنم و آن جایزه ها رو فقط تله ای برای شناسایی مجرمین و دزدان میدونم و از خیرش گذشتم :biggrin::).


ولی خوب جدای از شوخی میلیونها سیب هروز از درخت می افنتد پایین ولی فقط یکی به این افتادن دقت کرد :surprised:.
 
rf.ariyapoor

rf.ariyapoor

عضو جدید
دوست عزیز تو صورت مساله جای پرانتز ها جا بجا شده اگه می شه صورت مساله رو یه بار دیگه توضیح بده
 
dadvand

dadvand

عضو جدید
کد: 
 w(i)  ,  t(i)

بجای t(i) اشتباه k(i) درج شده . البته فرقی نداره در کل .
 
Z

zahra_1365

عضو جدید
سلام

همونطور که گفتین فکر نکنم کسی پیدا بشه بتونه حلش کنه خب چرااااااااااااااااااااااا خودتون برای ما حلش نمیکنین؟;)
 
dadvand

dadvand

عضو جدید
zahra jalili گفت:
سلام

همونطور که گفتین فکر نکنم کسی پیدا بشه بتونه حلش کنه خب چرااااااااااااااااااااااا خودتون برای ما حلش نمیکنین؟;)
کلیک کنید تا باز شود...

سلام .
من اگه حلش کرده بودم که اینجا نبودم :biggrin:.
من به شوخی اونجا گفتم حلش کردم خواستم یک مزاحی کرده باشم :D.
ولی دونستن این مسائل برای یک متخصص کامپیوتر بی نفع نیست .
البته برای حل این مسئله روشهایی وجود داره ولی نه با پیچیدگی چند جمله بلکه نمایی یعنی برای مثلا 100 قلم جنس ممکنه حلش هزاران سال با کامپیوتر طول بکشه .
روشها : برنامه نویسی پویا ، راهبرد شاخه و حد ، ....
 
oxision

oxision

عضو جدید
کاربر ممتاز
منم چون زبانم خوب نیست حاضر به مصاحبه نیستم :biggrin:
ولی میتونم ثابت کنم که زمانش از مرتبه (nlog n) میشه (البته منکه نه ، ولی قبلا ثابت شده ;))
 
dadvand

dadvand

عضو جدید
oxision گفت:
منم چون زبانم خوب نیست حاضر به مصاحبه نیستم :biggrin:
ولی میتونم ثابت کنم که زمانش از مرتبه (nlog n) میشه (البته منکه نه ، ولی قبلا ثابت شده ;))
کلیک کنید تا باز شود...

:eek:
قبلا ثابت شده که از مرتبه nLog n است ؟ شوخی میکنی ؟:D:D

این فایل رو ببین .در مورد سری مسائل NP است .
توی همین فایل صحبت اون 1 میلیون دلار هم شده :cool::).
موفق باشی ;);)
 

پیوست ها

  • lecture17ALGsummary.rar
    68.4 کیلوبایت · بازدیدها: 0
oxision

oxision

عضو جدید
کاربر ممتاز
جایزه رو تنهایی نگیرینا :biggrin: منم هستم
نمیدونم کدوم دانشگاه و شهر درس خوندی یا می خونی. اگه کتاب طراحی الگوریتم ها نوشته دکتر محمود نقیب زاده صفحه 159 الگوریتم رو به روش حریصانه نوشته. کل زمانیکه این الگوریتم نیاز دارد به زمان مرتب سازی محدود می شه که بهترین روش مرتب سازی هم از مرتبه n log n هست.
اگه کتاب رو پیدا نکردی بگو تا الگوریتم رو تایپ کنم :)
 
dadvand

dadvand

عضو جدید
oxision گفت:
جایزه رو تنهایی نگیرینا :biggrin: منم هستم
نمیدونم کدوم دانشگاه و شهر درس خوندی یا می خونی. اگه کتاب طراحی الگوریتم ها نوشته دکتر محمود نقیب زاده صفحه 159 الگوریتم رو به روش حریصانه نوشته. کل زمانیکه این الگوریتم نیاز دارد به زمان مرتب سازی محدود می شه که بهترین روش مرتب سازی هم از مرتبه n log n هست.
اگه کتاب رو پیدا نکردی بگو تا الگوریتم رو تایپ کنم :)
کلیک کنید تا باز شود...

سلام دوست عزیز . اشتباه متوجه شدی .
اون کوله پشتی کسری است ، این کوله پشتی صفر و یک است ، ما که توی دوران تحصیل مجبور بودیم مرجع انگلیسی بخونیم و اون ترجمه رو نخوندیم ولی فکر میکنم حتما در اون کتاب در مورد هر دوش بحث شده .

;):)
 
dadvand

dadvand

عضو جدید
oxision گفت:
جایزه رو تنهایی نگیرینا :biggrin: منم هستم
نمیدونم کدوم دانشگاه و شهر درس خوندی یا می خونی. اگه کتاب طراحی الگوریتم ها نوشته دکتر محمود نقیب زاده صفحه 159 الگوریتم رو به روش حریصانه نوشته. کل زمانیکه این الگوریتم نیاز دارد به زمان مرتب سازی محدود می شه که بهترین روش مرتب سازی هم از مرتبه n log n هست.
اگه کتاب رو پیدا نکردی بگو تا الگوریتم رو تایپ کنم :)
کلیک کنید تا باز شود...

لازم به تایپ الگوریتم نیست فقط حل مثال دوم رو با greedy method (روش حریصانه) حل کن .:confused::surprised::eek:

;)
 
A

azizi1485

عضو جدید
دوست عزیز هیچی نیست که حل نشه ولی فعلا علم ما آونقدر رشد نکرده .اصولا دانشمندا واسه پول کار نمی کنن واسه پیشرفت بشر زحمت میکشن من امیدوارم تا موقعه ای که زنده ام این مسئله حل شه.
 
PC-ENG

PC-ENG

عضو جدید
با سلام
یک سوال داشتم در دو تا مثالی که حل کرده اید چه جوری اون حالتها را به عنوان جواب انتخاب کردید

کد: 
مثال 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
 
dadvand

dadvand

عضو جدید
PC-ENG گفت:
با سلام
یک سوال داشتم در دو تا مثالی که حل کرده اید چه جوری اون حالتها را به عنوان جواب انتخاب کردید

کد: 
مثال 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
کلیک کنید تا باز شود...

مثال 2 : گنجایش حداکثر کوله پشتی W=16 (مثلا کیلوگرم ) است . با انتخاب جنس اول و سوم ارزش کل 90= 50+40= t1+t3 حاصل میشود و وزن آنها 12= 10 + 2= w1+w3
و کوچکتر از 16 یعنی ظرفیت کل کوله پشتی است . بعد از آن هر جنسی انتخاب شود وزن کل بیشتر از گنجایش کوله پشتی است و کوله پشتی پاره میشود (فرض صورت مسئله) .هر حالتی دیگری را شما در نظر بگیرید ارزش کل کمتر از 90 است . مثلا t2,t3 یا t3,t4 یا t1,t2,t4 ... یعنی تمام زیر مجموعه های اجناس را باید در نظر گرفت یعنی (تعداد nعضو) ^ 2 حالت . البته برای حل این مسئله و مسائل مشابه الگوریتمهای ارائه شده (برنامه نویسی پویا ، عقب گرد ، راهبرد شاخه و حد )که البته در بدترین حالت باز هم از پیچیدگی نمایی برخوردار است ولی در حالت میانگین بهتر از نمایی هستند ولی ارائه این الگوریتمها راه حل دلخواه این مسائل نیست چرا که مثلا برای یک نمونه 100 تایی این الگوریتمها باز هم ممکن است حل آنها توسط کامپیوتر سالیان سال به طول انجامد .:)
این گونه مسائل کاربردهای فراوانی در کامپیوتر ، صنعت ، اقتصاد .... دارند .


مثال 1: مشابه همین است ولی چون تعداد جنسهابیشتر است کمی شلوغ میشود .دراین مثال باید 32= 5 ^ 2 حالت را در نظر گرفت .
در مثال قبلی 16 حالت را باید در نظر گرفت .

;)
راستی نمیدونم چرا جناب oxision قهر کردن دیگه نمیان سر بزنند :smile:.
 
آخرین ویرایش:
sepehrkhosrowdad

sepehrkhosrowdad

مدیر بازنشسته
سلام.
کسی حاضره به 1مبتدی (مثل من) برنامه نویسی یاد بده؟!:)
قول میدم وقتی مسئله رو حل کردم، پول رو با استادم 50-50 نصف کنم!!!:surprised:
من پول می خوام!:cry:
میگن، نوآموزان، افکار خلاقتری دارن!!
 
PC-ENG

PC-ENG

عضو جدید
من در یک کتاب طراحی الگوریتم سه تا الگوریتم برای ابن مساله دیدم که با سه تا روش مختلف بود که بهترین مرتبه زمانی که تا به حال برای پیدا شده 2 به توان n/2 است . آیا این جایزه را برای مرتبه زمانی کمتر می دهند؟
 
dadvand

dadvand

عضو جدید
PC-ENG گفت:
من در یک کتاب طراحی الگوریتم سه تا الگوریتم برای ابن مساله دیدم که با سه تا روش مختلف بود که بهترین مرتبه زمانی که تا به حال برای پیدا شده 2 به توان n/2 است . آیا این جایزه را برای مرتبه زمانی کمتر می دهند؟
کلیک کنید تا باز شود...

سلام
اگه تو کتاب هست که پس باید به عنوان کاشف جایزه بهت بدن :D. شوخی میکنم .
یک سوال : در بدترین حالت 2 به توان n/2 است ؟؟؟
خیلی ممنون میشم اگه شبه الگوریتمش رو اینجا واسم بذاری یا اسمش رو بگی خودم پیدا کنم . خیلی مشتاق شدم البته الان که گفتی من خودم سرچ میکنم ولی باز هم اگه زحمت شما نیست و کتاب هم در حال حاضر دارین ، واسم فقط هم شبه الگوریتمش رو بذارین . ممنون :)

البته باز هم نمایی محسوب میشود ولی خوب بهتر از 2 به n (الگوریتمی که همه زیر مجموعه ها رو چک میکند ) است یا بهتر از ! n*n (بدترین حالت از روش برنامه نویسی پویا) است .
نمیدونم به کمتر (ولی باز هم نمایی) جایزه بدن یا نه . ولی جایزه رو به کسی میدن که یا یک الگوریتم چند جمله ای ارائه کنه یا ثابت کنه که غبر ممکن است .
موفق باشی ;)
 
آخرین ویرایش:
dadvand

dadvand

عضو جدید
sepehrkhosrowdad گفت:
سلام.
کسی حاضره به 1مبتدی (مثل من) برنامه نویسی یاد بده؟!:)
قول میدم وقتی مسئله رو حل کردم، پول رو با استادم 50-50 نصف کنم!!!:surprised:
من پول می خوام!:cry:
میگن، نوآموزان، افکار خلاقتری دارن!!
کلیک کنید تا باز شود...
:biggrin:
سلام .
مگه درس برنامه نویسی ندارین یا اگه در دوران دبیرستان چیزی از برنامه نویسی و الگوریتم نویسی یادتون هست همون کافی است .
مهم فقط ارائه یک الگوریتم است .:)
شرایطی که الگوریتم دارای پیچیدگی چند جمله ای باشه رو هم در پست اول گفتم .

منتظر شکوفایی استعدادهای شما هستیم :D:)
موفق باشی ;)
یادت نره ها جایزه نصف نصف . تو مصابحه در CNN هم باید از من به عنوان مشوقت اسم ببری .:biggrin:
 
PC-ENG

PC-ENG

عضو جدید
منبع کتاب طراحی الگوریتم جعفر نژاد قمی :

این شبه کد به زبان ++C که از روش الگوریتم عقبگرد استفاده کرده است

کد: 
void  knapsack(index i, int profit, int weight)
{
 if (weight <= w && profit > maxprofit)    //This set is best so far
 {
  maxprofit = profit;
  numbest = i;     //Set numbest to number
  bestset = include;     //Of items considered. Set bestset to this solution.
 }
 if (prmising(i))
 {
  include[i+1] = "yes"; //Include w[i+1]
  knapsack(i+1, profit + p[i+1], weight + w[i+1]);
  include[i+1] = "no";    //Do not include w[i+1]
  knapsack(i+1, profit, weight);
 }
}
bool promising(index i)
{
 index j, k;
 int totweight;
 float bound;
 if (weight >= W)    //Node is promising only
  return false;    //If we should  expand to
 else         //its children. There must
 {                   //be some capacity left for
  j = i+1;          //the children
  bound = profit;
  totweigth = weight;
  while (j <= n && totweight + w[j] <= W)
  {                                      //Grab as many items as
   totweight = totweight + W[j];       //possible
   bound = bound + p[j];
   j++;
  }
  k = j;         //Use k for consistency
  if(k <= n)       //whit formula in text
   bound = bound + ( W - totweight * p[k] / w[k];   //Grab fraction of kth item
  return bound > maxprofit;
 }
}
یک چیز دیگه چند سال پیش در دوران خوش دبیرستان از طریق انجمن ریاضی ایران متوجه شدم موسسه کلی آمریکا هفت میلیون دلار برای حل هفت مساله گذاشته بود که چهار تا از اون ها اگر اشتباه نکرده باشم مربوط به طراحی الگوریتم بود یکیش که یادم مونده مساله N و NP بود اگر کسی خبری درباره این مسابقه داره ممنون می شوم یه خبری به ما هم بده​
 
dadvand

dadvand

عضو جدید
PC-ENG گفت:
منبع کتاب طراحی الگوریتم جعفر نژاد قمی :

این شبه کد به زبان ++C که از روش الگوریتم عقبگرد استفاده کرده است

کد: 
void  knapsack(index i, int profit, int weight)
{
 if (weight <= w && profit > maxprofit)    //This set is best so far
 {
  maxprofit = profit;
  numbest = i;     //Set numbest to number
  bestset = include;     //Of items considered. Set bestset to this solution.
 }
 if (prmising(i))
 {
  include[i+1] = "yes"; //Include w[i+1]
  knapsack(i+1, profit + p[i+1], weight + w[i+1]);
  include[i+1] = "no";    //Do not include w[i+1]
  knapsack(i+1, profit, weight);
 }
}
bool promising(index i)
{
 index j, k;
 int totweight;
 float bound;
 if (weight >= W)    //Node is promising only
  return false;    //If we should  expand to
 else         //its children. There must
 {                   //be some capacity left for
  j = i+1;          //the children
  bound = profit;
  totweigth = weight;
  while (j <= n && totweight + w[j] <= W)
  {                                      //Grab as many items as
   totweight = totweight + W[j];       //possible
   bound = bound + p[j];
   j++;
  }
  k = j;         //Use k for consistency
  if(k <= n)       //whit formula in text
   bound = bound + ( W - totweight * p[k] / w[k];   //Grab fraction of kth item
  return bound > maxprofit;
 }
}
یک چیز دیگه چند سال پیش در دوران خوش دبیرستان از طریق انجمن ریاضی ایران متوجه شدم موسسه کلی آمریکا هفت میلیون دلار برای حل هفت مساله گذاشته بود که چهار تا از اون ها اگر اشتباه نکرده باشم مربوط به طراحی الگوریتم بود یکیش که یادم مونده مساله N و NP بود اگر کسی خبری درباره این مسابقه داره ممنون می شوم یه خبری به ما هم بده​
کلیک کنید تا باز شود...
واقعا تشکر میکنم از زحمتی که کشیدی . فقط یک اشتباه خیلی کوچیک رخ داده ، راه برد عقبگرد رو من اشنا هستم ، برای اطمینان هم دوباره مراجعه کردم ، پیچیدگی آن در بدترین حالت بازهم 2 به توان n هست و آن وقتی پیش میاد که
کد: 
W=n
t(i)=1 
w(i)=1
1<= i <=n-1
t(n)=n
w(n)=n
در این حالت تمام درخت فضای حالت چک میشه که تعداد اون 2 به توان n+1 است.شاید اشتباه چاپی در اون کتاب هست .
باز هم از زحمتی که کشیدی تشکر میکنم .:)
اگه منظورت claymath است آره در فایل پیوست صفحه قبل یک پاورپوینت هست از سایت همون موسسه دانلود کردم .
برای هر سوال یک میلیون دلار میده .
یک سوال دیگش در مورد اعداد اول است .
 
PC-ENG

PC-ENG

عضو جدید
شرمنده ام سوالتون خوب متوجه نشده بودم اون الگوریتم که مرتبه زمانیش 2 به توان n/2 هست داخل کتاب نگفته فقط این پتوضیح رو نوشته که هوروویتز و شانی (1974) روش تقسیم و حل را با روش برنامه نویسی پویا ترکیب کرده والگوریتمی برای مساله کوله پشتی بسط داده اند که در بدترین حالت به صورت فوق است
 
oxision

oxision

عضو جدید
کاربر ممتاز
نه بابا چرا قهر کنم. وقت کم بود و نرسیدم. چندتا پروژه matlab دارم که باید تا آخر ماه تحویل بدم.
اینم اصل الگوریتم که به روش کسری هست. همونطوریکه شما فرمودید:
کد: 
[FONT=Times New Roman][SIZE=3]Void gknapsack(float P[],float W[], float M, floa X[],int n)[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]{[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Float rc;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Int I;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Pwsort(P,W,n);[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]For(i=0;i<n;i++)[/SIZE][/FONT]
[SIZE=3][FONT=Times New Roman]   X[i]=0;[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3]Rc=M;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]For(i=0;i<n;i++0[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]{[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]If (W[i]>rc)[/SIZE][/FONT]
[SIZE=3][FONT=Times New Roman]   Break;[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3]X[i]=1;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Rc=rc-W[i];[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]}[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]If ( i<=n-1)[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]X[i]=rc/W[i];[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]}[/SIZE][/FONT]
[LEFT]
در ضمن داداش عزیزم ، دکتر نقیب زاده خودشون این کتاب رو تالیف کردند و ترجمه نیست. ایشون چند ساله به درجه استادی رسیدند.
آقا یاسین کجاست ، سخنان تکمیلی رو بگه :w20:
[/LEFT]
 
آخرین ویرایش:
dadvand

dadvand

عضو جدید
oxision گفت:
نه بابا چرا قهر کنم. وقت کم بود و نرسیدم. چندتا پروژه matlab دارم که باید تا آخر ماه تحویل بدم.
اینم اصل الگوریتم که به روش کسری هست. همونطوریکه شما فرمودید:
کد: 
[FONT=Times New Roman][SIZE=3]Void gknapsack(float P[],float W[], float M, floa X[],int n)[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]{[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Float rc;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Int I;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Pwsort(P,W,n);[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]For(i=0;i<n;i++)[/SIZE][/FONT]
[SIZE=3][FONT=Times New Roman]   X[i]=0;[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3]Rc=M;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]For(i=0;i<n;i++0[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]{[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]If (W[i]>rc)[/SIZE][/FONT]
[SIZE=3][FONT=Times New Roman]   Break;[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3]X[i]=1;[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Rc=rc-W[i];[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]}[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]If ( i<=n-1)[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]X[i]=rc/W[i];[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]}[/SIZE][/FONT]
در ضمن داداش عزیزم ، دکتر نقیب زاده خودشون این کتاب رو تالیف کردند و ترجمه نیست. ایشون چند ساله به درجه استادی رسیدند.
آقا یاسین کجاست ، سخنان تکمیلی رو بگه :w20:
​
کلیک کنید تا باز شود...

استغفرالله . مگه ما در اون حدی هستیم که به آقای دکتر اشکال بگیریم . من به شما گفتم که هر دوش حتما در کتاب هست و شما احتمالا در کتاب درست دقت نکردید و حتی با وجود اینکه کتاب رو نه خوندم و نه حتی دیدم مطمئن بودم که اصل مسئله رو(کوله پشتی صفر ویک) داره . چون اصل این مسئله در مورد کوله پشتی صفر یک است است و کوله پشتی کسری در جایی مطرح میشه که : میخواد نشون بده که با روش حریصانه کوله پشتی صفر و یک قابل حل نیست که با چند تا مثال نقض براحتی قابل اثبات است . ولی سپس میگه اگر دزد میتونست کسری از اجناس رو برداره (مثلا خاک طلا) اونوقت میشد از روش حریصانه استفاده کرد که به اون کوله پشتی کسری میگن . در کل اصلا کوله پشتی کسری مطرح نیست و مسئله ای ساده و بدیهی است . ما ترم اولمون با وجود اینکه نمیدونستیم اصلا طراحی الگوریتم چی هست شکلی از این رو (کوله پشتی کسری) در امتحان پایان ترم داشتیم و همین طور که شما گفتین از طریق مرتب سازی بسادگی قابل حل است .

موفق باشی .;):)
 
آخرین ویرایش:
dadvand

dadvand

عضو جدید
PC-ENG گفت:
شرمنده ام سوالتون خوب متوجه نشده بودم اون الگوریتم که مرتبه زمانیش 2 به توان n/2 هست داخل کتاب نگفته فقط این پتوضیح رو نوشته که هوروویتز و شانی (1974) روش تقسیم و حل را با روش برنامه نویسی پویا ترکیب کرده والگوریتمی برای مساله کوله پشتی بسط داده اند که در بدترین حالت به صورت فوق است
کلیک کنید تا باز شود...

مرسی - همین دو اسم هم کافیست . ممنون .;)

موفق و پیروز باشی ;):)
 
H

hamid2014.a

عضو جدید
سلام آقای dadvand.
دمت گرم. واقعاً با حال بود.
آقا ما آخرش نفهمیدیم بهترین پیچیدگی محاسباتی که تا حالا ارائه دادن چنده؟
آیا باز هم این مسئله از لحاظ پیچیدگی مکانی (فضای لازم برای محاسبات) محدودیت داره یا نه؟ یعنی اگر این مسئله به NP-space تبدیل بشه آیا باز هم حل اون ارزش داره؟
یه خواهش دیگه هم داشتم اینکه آیا امکانش هست که کدهای حل این مسئله رو با زبان MATLAB هم بزارین؟ خیلی ممنون میشم چون من فقط متلب بلدم.
 
H

hosein384

عضو جدید
همچین میگی یکی بیاد حلش کنه دیگه .. انگار جدول ضربه....
نه خانم خوندن صورت مسئله سخته چه برسه به حلش...
 
برای ارسال پاسخ شما باید وارد سیستم شوید.
بالا