PDA

View Full Version : سوال: بهینه سازی



بهزاد
پنج شنبه 25 شهریور 1389, 21:35 عصر
با سلام
ما چند تا لیوان داریم که هر کدام ظرفیت خاصی دارند می خواهیم با چند نوع مایع مختلف که هر کدام حجم مشخصی دارند این لیوان ها را پر کنیم .
سوال : بهترین حالتی که از کمترین ظرف استفاده بشه چیه ؟
فرض : مایعات قاطی نمیشن - ترتیب مهم نیست -

shecarchi
پنج شنبه 25 شهریور 1389, 21:38 عصر
همه رو با هم مخلوط میکنیم میریزیم داخل بزرگترین ظرف اگه سرریز کرد بقیشو میریزیم تو ظرف بعدی

بهزاد
سه شنبه 13 مهر 1389, 20:39 عصر
کسی نبود ؟؟؟؟؟؟؟؟؟؟/

مسعود اقدسی فام
سه شنبه 13 مهر 1389, 23:30 عصر
با سلام
ما چند تا لیوان داریم که هر کدام ظرفیت خاصی دارند می خواهیم با چند نوع مایع مختلف که هر کدام حجم مشخصی دارند این لیوان ها را پر کنیم .
سوال : بهترین حالتی که از کمترین ظرف استفاده بشه چیه ؟
فرض : مایعات قاطی نمیشن - ترتیب مهم نیست -

یه مایع رو نمی شه توی دو تا لیوان ریخت؟ هر مایع فقط یه لیوان؟

و توی یه لیوان می شه چند مایع رو ریخت؟

بهزاد
یک شنبه 02 آبان 1389, 12:05 عصر
هر مايع فقط توي يه ليوان .
توي هر ليوان هر چقد كه ظرفيتش رو داشته باشه .
اينجا فقط مايع و ليوان يه مثال بود اون ميتونه چند تكه درخت با طول متفاوت و جعبه با ظرفيت طولي متفائت باشه .

مسعود اقدسی فام
یک شنبه 02 آبان 1389, 19:46 عصر
هر مايع فقط توي يه ليوان .
توي هر ليوان هر چقد كه ظرفيتش رو داشته باشه .
اينجا فقط مايع و ليوان يه مثال بود اون ميتونه چند تكه درخت با طول متفاوت و جعبه با ظرفيت طولي متفائت باشه .

چیزی که الان به ذهنم می‌رسه:

مایعات و لیوان‌ها رو بر حسب حجم و ظرفیت مرتب کن.

از بزرگترین لیوان شروع کن و مایعات رو به ترتیب از حجم زیاد به حجم کم داخلش بریز. اگه به مایعی برخورد کردی که حجمش از حجم باقیمانده لیوان بیشتر بودٰ ازش رد شو و مایع بعدی رو امتحان کن. به همین ترتیب پیش برو تا لیوان اول پر بشه. لیوان بزرگتر بعدی رو هم با شروع از پر حجم‌ترین مایع باقیمانده دوباره با همین روال پر کن.

مثلا:

پنج تا لیوان با ظرفیت‌های 5 و 10 و 15 و 20 و 25 داریم.

شش تا مایع با حجم‌های 1 و 2 و 3 و 5 و 6 و 8 و 10 داریم.

مایع 10 و 8 و 6 رو وارد لیوان 25 می‌کنیم. دیگه نمی‌شه مایع 5 رو وارد کنیم. مایع‌های با حجم کمتر رو امتحان می‌کنیم تا می‌رسیم به آخری. همون یک رو می‌شه وارد کرد. پس یک هم وارد می‌شه. لیوان بعدی رو هم به همین ترتیب با شروع از مایع 5 پر می‌کنیم.

به نظر این روش بهینه‌ترین حالت می‌یاد. چون سعی می‌کنیم فضای باقیمونده لیوان رو با پرحجم‌ترین مایع موجود پر کنیم. چون ممکنه این مایع تو لیوان کوچکتر بعدی اصلا جا نشه. یه جورایی جزو الگوریتم‌های حریصانه هستش.

حالا بازم روش فکر می کنم. شما هم فکر کن.

armiya
دوشنبه 03 آبان 1389, 23:52 عصر
ببینید این جور سوالات راه حل گسسته ای دارند و الگوریتمیک خوب ولی سوال شما کلی ابهام داره بنا براین اگه واضح تر مطرح کنی بهتره