حلولي في كودرهب

جمع النجوم البراقة

صعب20 نقطةرياضياتPython

الوصف

في ليلة صيفية صافية، صعد ليث قمة جبل ليجمع نجوم السماء في قارورة سحرية. كل نجمة لها لمعان معيّن (رقم صحيح)، والقارورة تتحمل لمعة إجمالية لا تتجاوز قيمة محدّدة. ليث يريد أن يملأ قارورته بأكثر لمعان ممكن دون تجاوز السعة.

لكل نجمة قيمة لمعانٍ (مثل 5، 3، 8، 6، 2) وسعة القارورة مثلاً 14.

  • إذا جمع ليث النجمتين اللتين لمعانهما 8 و6، تصبح مجموع اللمعان 14 (أقصى حدّ).

  • لو حاول جمع 8 + 5 + 3 = 16 فلن تناسب القارورة.

مهمتك أن تُساعد ليث في اختيار مجموعة النجوم التي يلتقطها لتمتلئ قارورته بأكبر لمعان ممكن دون تجاوز السعة.

كيف تساعده في هذا التحدي؟

هذا هو مشكلة حقيبة الظهر (0/1 Knapsack) الشهيرة، ويمكنك معالجتها بخطوات:

  • تمثيل المشكلة ديناميكيًا

  • أنشئ مصفوفة dp بحجم (capacity+1) حيث dp[s] = true إذا كان بالإمكان تحقيق لمعان مجموعه s باستخدام بعض النجوم.

  • التحديث العكسي

  • لكل نجمة بمعانٍ b، مرّ في s من capacity نزولًا إلى b وعلّم dp[s] = dp[s] || dp[s - b]

  • هذا يضمن أنك لا تستخدم النجمة نفسها أكثر من مرة.

  • إيجاد أفضل لمعة

  • ابحث عن أكبر s ≤ capacity حيث dp[s] صواب (true).

  • هذا s هو أقصى لمعان يمكنك جمعه.

  • إعادة بناء الحلّ

  • احتفظ بمصفوفة موازية prev[s] تخبرك أي نجمة (أي فهرس) أدّت للوصول إلى s.

  • تبدأ من أفضل s وترجع خطوة خطوة عبر prev لتجمع قائمة النجوم المختارة.

مثال توضيحي:

brightness = [5, 3, 8, 6, 2]

capacity = 14

  • نبدأ بـ dp[0] = true (بدون نجوم نجمع لمعان صفر).

  • نمعالج النجمة 5: نعلّم dp[5] = true.

  • ثم النجمة 3: نعلّم dp[8] = true (لأن 5+3) و dp[3] = true.

  • ثم النجمة 8: نعلّم dp[8] (من قبل) و dp[13] = true (5+8) و dp[11] = true (3+8).

  • تستمرّ حتى كل النجوم.

  • بعد انتهاء التحديثات، نبحث من s=14 نزولًا: نجده قابلًا (dp[14] = true).

  • عبر prev نكتشف أنّ 14 جاء من جمع 8 و6.

  • إذًا المجموعة المختارة هي [8, 6].

أمثلة

المدخلاتالمخرجات المتوقعة
brightness = [5,3,8,6,2]، capacity = 14[6,8]
brightness = [5,5,5,5]، capacity = 10[5,5]
brightness = [1,2,3,2]، capacity = 5[2,3]
brightness = [9,1,5]، capacity = 8[1,5]

جرّب تحله في كودرهب

الحل

from typing import List
def collectStars(brightness: List[int], capacity: int) -> List[int]:
    brightness = sorted(brightness, reverse=True)
    dp = [False] * (capacity + 1)
    dp[0] = True
    parent = {}
    for i, b in enumerate(brightness):
        for s in range(capacity, b - 1, -1):
            if not dp[s] and dp[s - b]:
                dp[s] = True
                if s not in parent:
                    parent[s] = (s - b, b)
    max_s = capacity
    while max_s > 0 and not dp[max_s]:
        max_s -= 1
    ans = []
    curr = max_s
    while curr > 0:
        prev, item = parent[curr]
        ans.append(item)
        curr = prev
    return sorted(ans)

في هذه الصفحة