جمع النجوم البراقة
الوصف
في ليلة صيفية صافية، صعد ليث قمة جبل ليجمع نجوم السماء في قارورة سحرية. كل نجمة لها لمعان معيّن (رقم صحيح)، والقارورة تتحمل لمعة إجمالية لا تتجاوز قيمة محدّدة. ليث يريد أن يملأ قارورته بأكثر لمعان ممكن دون تجاوز السعة.
لكل نجمة قيمة لمعانٍ (مثل 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)