الحد الأقصى لعدد المجموعات المماثلة من حجم معين يمكن إجراؤها من صفيف معين

Question

أنا أعطيت مجموعة من الأرقام، وليس الفريدة بالضرورة وحجم المجموعة. دع الصفيف يشار إلى $ B $ وحجم المجموعة يكون $ $ .

أحتاج إلى العثور على الحد الأقصى لعدد المجموعات ذات المحتويات بالضبط بنفس المحتويات وحجم $ $ يمكن تصنيعها من عناصر $ B $ . بمجرد استخدام عنصر في المجموعة، يتم استنفاده. يمكن أن تحتوي المجموعة على أكثر من عنصر واحد بنفس القيمة طالما أن العنصر لا يزال متاحا في $ B $ .

مثال:

1. إذا كانت صفيف الإدخال $ \ {1، 2، 3، 1، 2، 3، 4 \} $ ، وحجم المجموعة هو 3 دولارات $ الحد الأقصى لعدد المجموعات التي يمكن صنعها هي $ 2 $ ، والتي هي $ \ {1، 2، 3 \} $ و $ \ {1، 2، 3 \} $ .
2. إذا كانت صفيف الإدخال هي $ \ {1، 3، 3، 3، 6، 3، 10 \} $ ، وحجم المجموعة هو $ 4 $ الحد الأقصى لعدد المجموعات التي يمكن صنعها هي $ 1 $ ، والتي هي $ \ {1، 3، 3، 3 \} $ .

ما حاولت حتى الآن، هو تأطير بعض المعادلات (الواردة أدناه) ولكن بعد ذلك، أنا أكافح من أجل التوصل إلى خوارزمية لحلها.

دع $ f_1 $ يكون تردد العنصر $ b_1 $ ، $ f_2 $ تكون وتيرة عنصر $ b_2 $ وهلم جرا حتى $ B_N $ ، حيث $ b_1 \ dots B_N $ هي عناصر مميزة من الصفيف $ B $ .

الآن أحتاج إلى اختيار $ n_1، n_2، \ dots n_i $ مثل

1. $ n_1 + n_2 + \ dots + n_i= $
2. $ k \ cdot n_1 \ leq f_1 \ text {،} k \ cdot n_2 \ leq f_2 \ text {،} \ dots \ text {،} k \ cdot n_i \ leq f_i $
3. $ K $ هو عدد المجموعات ونحن بحاجة إلى زيادة ذلك.

طول $ B $ يمكن أن يكون كبيرا مثل 10 دولارات ^ 5 $ و $ $ كبيرة مثل 10 دولارات ^ 5 $ .

الرجاء مساعدتي في العثور على نهج جشع أو ديناميكي للمشكلة.

Answer 1

الوظيفة $$ f: \ mathbb {n} \ rawrow \ {0، 1 \}: f (k)= \ ابدأ {الحالات} 1؛ & \ text {إذا كان هناك حل من حجم $ K $،} \\ 0؛ & \ text {خلاف ذلك} \ نهاية {الحالات} $ هو Monoton، لأنه إذا لم يكن هناك حل من الحجم $ K $ ثم لا يوجد حل من الحجم $ k + 1 $ . هذا يعني أننا نتمكن من البحث الثنائي قيمة $ k $ في الفاصل الزمني $ [1، | B |] $ وإخراج أعظم $ K $ بالنسبة له حل حجم $ K $ . وبالتالي، حولنا المشكلة إلى مشكلة في القرار مع $ o (\ log | b |) $ factor في وقت التشغيل.

للحصول على قيمة ثابتة ل $ K $ ، يكفي الحل الجشع. إذا كان لدينا $ f_i $ نسخ من بعض العناصر $ b_i $ ، ثم يمكن أن تحتوي كل مجموعة على $ \ Lfloor \ lfloor \ frac {k} \ right \ rfloor $ من هذا العنصر. لذلك لدينا حل من حجم $ k $ إذا وفقط إذا $$ \ sum \ limits_ {i= 1} ^ {n} \ left \ lalloor \ frac {k} \ right \ rfloor \ geq a. $

كممارسة، حاول إثبات أن الحل الجشع هو الأمثل. يمكن حدودا وقت التشغيل في $ O (| B | \ Log | B |). $