سلام . از اونجایی که تو این دو روز فقط 2 نفر سوالای جستجوی دودویی رو حل کردن و بقیه اکثرا wrong میگیرن تو این مسئله ها ، میخوام سوال اول رو که ترکیبی از جستجوی دودویی و روش حریصانه هست رو به عنوان نمونه حل کنم :


تعریف مجموعه ی k-multipl free : مجموعه ای هستش که ... هیچ دو عضوی ازش پیدا نکنیم که رابطه ی x = y*k برقرار باشه . در واقع هیچ عددی ضریب k هیچ عدد دیگه ای نباشه .

روی سوال میگه یه مجموعه (مثلا S) داریم و یه عدد k .

سایز بزرگترین زیر مجموعه ی ممکن از مجموعه ی داده شده که k-multiple free هستش چنده ؟


حل : بیاین برای حل مسئله اول مجموعه رو صعودی مرتب کنیم و بجای ساختن زیر مجموعه با انتخاب عضوها از مجموعه S ، عضوهای مشکل ساز مجموعه ی S رو حذف کنیم تا تبدیل به زیرمجموعه ای از خودش بشه . برای این کار بیاین عضوها رو دونه دونه بررسی کنیم ، دو حالت داریم :


1 - ضریب kام عضو x داخل مجموعه نیست : در اینصورت با این عضو مشکلی نداریم و این عضو حتما باید داخل جواب نهاییمون باشه .

2 - ضریب kام عضو x یعنی y وجود داره : خب ما نمیتونیم هر دوتای اینارو داخل مجموعه نگه داریم . میدونیم اگه یکی از عضوهارو حذف کنیم مشکل این مورد حل میشه ولی کدوم ؟

بزارین با مثال توضیح بدم : فرض کنین S = 4,8,16 و k = 2 .

رابطه 4*2 = 8 برقراره و ما میخوایم یکی از اینارو حذف کنیم . حالا اگه 4 رو حذف کنیم و 8 رو نگه داریم به این مشکل میخوریم که رابطه 8*2=16 هم برقراره و بازم باید یکی از این دوتا رو حذف کنیم ! ولی اگه 8 رو حذف کنیم و 4 رو نگه داریم دیگه مطمئنیم که 4 نمیتونه دوباره برامون دردسرساز بشه و کس دیگه ای رو حذف کنه .

پس نتیجه اینکه باید y رو حذف کنیم .


با انجام این دو مرحله برای تمام عضوها و حذف y های موجود به زیرمجموعه ای میرسیم که مطمئنیم بزرگترین زیرمجموعه ی ممکنه چون کاملا حریصانه با مسئله برخورد کردیم و کمترین حذف ممکن رو انجام دادیم.


برای پیدا کردن y ها میتونیم جستجوی دودیی بزنیم .

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