(۰۹ بهمن ۱۳۹۵ ۰۱:۰۶ ب.ظ)life24 نوشته شده توسط:  سلام
ما اگر بردار های زیر رو داشته باشیم
[۴ ۲]
[۵ ۳]
[۵ ۲]
[۴ ۳]

ساب ست سام ش میشه
۰۰۱۱ ۱۱۰۰
هدف اینکه زیر مجموعه هایی پیدا کنیم که جواب اون ۵۰ درصد مجموع سطر ها باشه
مثل مثال بالا
اما سوال اینجاست این
۰۰۱۱ ۱۱۰۰
از کجا امده؟ چجور حساب شده؟ به شیوه درختی حساب کردند
راستش من اصلا نمیفهمم منظور از
۰۰۱۱ ۱۱۰۰ چیه

به نظرم یه جور subset sum دو بعدی هست و احتمالاً منظورش این هست که تعدادی از مجموعه‌ها رو طوری انتخاب کنیم که مجموع xهاشون بشه نصف مجموع کل xها، و مجموع yهاشون بشه نصف مجموع کل yها. اینجا مجموع xها هست ۱۰ و مجموع yها هست ۱۸/ اگه دو مجموعه‌ی اول رو انتخاب کنیم، جمع xهاشون میشه ۵، جمع yهاشون میشه ۹ که شرط رو برقرار میکنه. همینطور اگه دو مجموعه‌ی دوم رو انتخاب کنیم.
جواب اول رو با ۱۱۰۰ که ۱ به معنی انتخاب مجموعه هست و ۰ عدم انتخاب، نشون داده. جواب دوم یعنی انتخاب مجموعه‌ی ۳ و ۴ رو هم با ۰۰۱۱ نشون داده.
البته مثالش خوب نیست و ابهام داره چون اعداد شبیه هم هستند و صرفا xها و yها رو در دو مجموعه‌ی آخری جابجا کرده ولی احتمال زیاد منظور همون هست که گفتم. در کل روی subset sum میشه شرط‌های مختلف گذاشت که اینجا هم این مدلی شرط گذاشته. مسأله هم NP-Complete هست ولی با برنامه‌ریزی پویا به نظرم حل بشه