تالار گفتمان مانشت

سلام
ما اگر بردار های زیر رو داشته باشیم
[4 2]
[5 3]
[5 2]
[4 3]

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

(09 بهمن 1395 01:06 ب.ظ)life24 نوشته شده توسط: [ -> ]سلام
ما اگر بردار های زیر رو داشته باشیم
[۴ ۲]
[۵ ۳]
[۵ ۲]
[۴ ۳]

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

به نظرم یه جور subset sum دو بعدی هست و احتمالاً منظورش این هست که تعدادی از مجموعه‌ها رو طوری انتخاب کنیم که مجموع xهاشون بشه نصف مجموع کل xها، و مجموع yهاشون بشه نصف مجموع کل yها. اینجا مجموع xها هست 10 و مجموع yها هست 18. اگه دو مجموعه‌ی اول رو انتخاب کنیم، جمع xهاشون میشه 5، جمع yهاشون میشه 9 که شرط رو برقرار میکنه. همینطور اگه دو مجموعه‌ی دوم رو انتخاب کنیم.
جواب اول رو با 1100 که 1 به معنی انتخاب مجموعه هست و 0 عدم انتخاب، نشون داده. جواب دوم یعنی انتخاب مجموعه‌ی 3 و 4 رو هم با 0011 نشون داده.
البته مثالش خوب نیست و ابهام داره چون اعداد شبیه هم هستند و صرفا xها و yها رو در دو مجموعه‌ی آخری جابجا کرده ولی احتمال زیاد منظور همون هست که گفتم. در کل روی subset sum میشه شرط‌های مختلف گذاشت که اینجا هم این مدلی شرط گذاشته. مسأله هم NP-Complete هست ولی با برنامه‌ریزی پویا به نظرم حل بشه