رفتن به مطلب

سوال: راه حل این مسئله چیست؟؟؟


ارسال های توصیه شده

سلام

 

یک سری عدد داریم به این صورت

 

[TABLE=width: 64]

[TR]

[TD=class: xl63, width: 64, align: right]2[/TD]

[/TR]

[TR]

[TD=class: xl63, align: right]3.2[/TD]

[/TR]

[TR]

[TD=class: xl63, align: right]1.8[/TD]

[/TR]

[TR]

[TD=class: xl63, align: right]4[/TD]

[/TR]

[TR]

[TD=class: xl63, align: right]6[/TD]

[/TR]

[TR]

[TD=class: xl63, align: right]9.1[/TD]

[/TR]

[TR]

[TD=class: xl63, align: right]5[/TD]

[/TR]

[/TABLE]

 

حالا می خواییم حالت هایی رو پیدا کنیم که با جمع این اعداد به مجموع 12 برسیم

 

مثلا با جمع 6 تا عدد دو میشه به 12 رسید پس جلوی 2 میذاریم 6 بقیه صفر یا

با جمع 2 و 4 و دو بار 6 میشه 12 یعنی جلوی عدد 2 و 4 ، 1 و جلوی عدد 6 میذاریم 1 و بقیه میشه صفر

 

حالا الگوریتم حل این مسئله چیه؟:ws38:

لینک به دیدگاه

یه سوالایی میپرسیا!

واللا نمیدونم...

در موردش فکر میکنم

بذار یکی رو هم دعوت میکنم شاید بلد باشه:w16:

لینک به دیدگاه
یه سوالایی میپرسیا!

واللا نمیدونم...

در موردش فکر میکنم

بذار یکی رو هم دعوت میکنم شاید بلد باشه:w16:

 

معمولا این جور مسائل اسم خاصی داره یک نوع مسئله OR محسوب میشه ولی خیلی وقته کار نکردم الان هنگم:icon_pf (34):

لینک به دیدگاه
درود

يه الگوريتم براي برنامه نويسي مي‌خواين يا جواب نهايي مد نظره؟

 

الگوریتم خو باشه بهتره ،ماهیگیری میخوام دیگه:ws3:

لینک به دیدگاه
مساله کوله پشتی هستش با طراحی الگوریتم حل نمیشه (بیشتر از نمایی هستش)

OR یادم رفته

ولی فکر نکنم با درجه یک حل بشه:ws3:

 

تو مسئله کوله پشتی ما یک ظرفیت داریم یکیم ارزش که حالت بهینه پیدا میشه اینجا ما فقط ظرفیت داریم و تمامی حالتارو میخوایم :ws38:

لینک به دیدگاه
تو مسئله کوله پشتی ما یک ظرفیت داریم یکیم ارزش که حالت بهینه پیدا میشه اینجا ما فقط ظرفیت داریم و تمامی حالتارو میخوایم :ws38:

 

اون اعداد تو جدول میشه ارزش هر کدوم

ظرفیت کل کیسه هم 12 است

البته خورد کردن سکه بیشتر می خوره:ws3: چون تعداد نامحدود از هر کدوم داریم:whistle:

لینک به دیدگاه
اون اعداد تو جدول میشه ارزش هر کدوم

ظرفیت کل کیسه هم 12 است

البته خورد کردن سکه بیشتر می خوره:ws3: چون تعداد نامحدود از هر کدوم داریم:whistle:

 

ما یک ارزش که بیشتر نداریم تو کوله پشتی ، مثلا ترکیب 4 ،2 ،6 ارزش کدوم میشه؟ گمان نکنم با کوله پشتی حل بشه

لینک به دیدگاه
ما یک ارزش که بیشتر نداریم تو کوله پشتی ، مثلا ترکیب 4 ،2 ،6 ارزش کدوم میشه؟ گمان نکنم با کوله پشتی حل بشه

اولش سوتی دادم

با کوله پشتی که نه ولی با خرد کردن سکه ها میشه ما می خواییم 12 تومن سکه رو با سکه های بالا بسازیم تو راه حل الگوریتمی بک ترک می زنیم به جای اینکه هرس کنیم به هر جواب که رسیدم ایندکس رو یکی زیاد می کنیم

لینک به دیدگاه
اولش سوتی دادم

با کوله پشتی که نه ولی با خرد کردن سکه ها میشه ما می خواییم 12 تومن سکه رو با سکه های بالا بسازیم تو راه حل الگوریتمی بک ترک می زنیم به جای اینکه هرس کنیم به هر جواب که رسیدم ایندکس رو یکی زیاد می کنیم

 

تو backtracking حالت صفر رو یک داره مثل مسئله 8 وزیر ولی اینجا صفر رو یک نیست یعنی با 6 تا 2 هم به جواب میرسیم :ws38:

لینک به دیدگاه
تو backtracking حالت صفر رو یک داره مثل مسئله 8 وزیر ولی اینجا صفر رو یک نیست یعنی با 6 تا 2 هم به جواب میرسیم :ws38:

کلا قاطیشون کردم:ws3:

ولی از همون راه حل سکه ها حل میشه

راه حل سکه ها تو کتابا هست الان یادم نیست دقیقا چون یه سکه 12 تایی رو میشه با 6 تا سکه ی 2 تایی تو اون سوال حل کرد یه سرچی درمورد خورد کردن سکه ها بزن خیلی معروفه

لینک به دیدگاه

بهینگی مد نظره یا فقط جمعشون 12 بشه؟

 

آخه از بهینگی چیزی نگفته .توی کوله پشتی یا هر الگوریتم پویای دیگه بهینگی بیشتر مد نظره

لینک به دیدگاه
سلام

با جمع 2 و 4 و دو بار 6 میشه 12 یعنی جلوی عدد 2 و 4 ، 1 و جلوی عدد 6 میذاریم 2 و بقیه میشه صفر

 

حالا الگوریتم حل این مسئله چیه؟:ws38:

 

این که نوشتی اشتباه نیست؟ جلوی 6 یه دونه 1 باشه

 

فقط میخوای مضرب صحیح ای باشه اگه اعشاری قبول کنه خیلی راحت جواب در میاد:ws3:

لینک به دیدگاه
این که نوشتی اشتباه نیست؟ جلوی 6 یه دونه 1 باشه

 

فقط میخوای مضرب صحیح ای باشه اگه اعشاری قبول کنه خیلی راحت جواب در میاد:ws3:

 

آره جلو 6 یک باشه ، مضرب صحیح باید باشه :ws38:

لینک به دیدگاه

اقا دیشب گیج بودم :ws3:(26 ساعت نخوابیده بودم)

الان نشستم فکر کردم یه راه حل خورد به ذهنم بررسی کن راه حله رو مشکل نداشته باشه چون بهینه رو نمی خوایم همه ی حالات رو می خوایم گریدی جواب نمیده

ما مبلغ nداریم با سکه هایی با ارزش m1,m2,....,mn

ما ابتدا تا می توانیم از با ارزش ترین سکه(mn) از مبلغ کل کم می کنیم و همین تابع را با مبلغ جدید و سکه ها ی زیر مبلغ الان صدا می زنیم وقتی تابع برگشت یکی از سکه ها ی با ارزش (mn ) کم می کنیم و تابع را صدا بزنیم(می شه یه حلقه که برای بیشترین تعداد سکه ی mn (که با ارزشترین سکه در این سطح می باشد ) تا صفر) شرط بازگشتش هم صفر شدن مبلغه که یکی به کل تعداد حالات جمع می کنه یه نوع بازگشت دیگه داریم که مبلغمون کمتر از بی ارزشترین سکه میشه که بدون اینکه به تعداد حالات چیزی اضافه کنیم بر می گردیم

به راحتی هم میشه داینامیکش کرد

لینک به دیدگاه

به گفتگو بپیوندید

هم اکنون می توانید مطلب خود را ارسال نمایید و بعداً ثبت نام کنید. اگر حساب کاربری دارید، برای ارسال با حساب کاربری خود اکنون وارد شوید .

مهمان
ارسال پاسخ به این موضوع ...

×   شما در حال چسباندن محتوایی با قالب بندی هستید.   حذف قالب بندی

  تنها استفاده از 75 اموجی مجاز می باشد.

×   لینک شما به صورت اتوماتیک جای گذاری شد.   نمایش به صورت لینک

×   محتوای قبلی شما بازگردانی شد.   پاک کردن محتوای ویرایشگر

×   شما مستقیما نمی توانید تصویر خود را قرار دهید. یا آن را اینجا بارگذاری کنید یا از یک URL قرار دهید.

×
×
  • اضافه کردن...