Fractional Knapsack

Q: ما هو التعقيد الزمني لمسألة الحقيبة الجزئية؟

ترتيب العناصر حسب القيمة لكل وزن يستغرق O(n log n) ، ويُجرى الملء في مرور واحد، لذا يكون الإجمالي O(n log n) مع مساحة O(n) للترتيب. يستغرق البحث عن العنصر الأعلى كثافةً في كل جولة O(n²) .

Q: كيف تحل مشكلة حقيبة الظهر الكسرية دون استخدام أعداد الفاصلة العائمة؟

مع الأوزان الموجبة، يكون الاختبار a / b > c / d مكافئًا للاختبار a × d > c × b ، لذا قارِن الكثافات بالضرب التبادلي. أفضل قيمة هي عدد صحيح مضافًا إليه كسر واحد، values[i] × room / weights[i] للعنصر الذي يُؤخذ جزء منه، لذا فإن قسمة صحيحة واحدة تعطي الإجابة المقربة إلى الأسفل بدقة.

متوسطالخوارزميات الجشعة الترتيب

+10

لديك n عناصر. قيمة العنصر i هي values[i] ووزنه weights[i]. تسع حقيبتك وزنًا إجماليًا لا يتجاوز capacity، ويمكنك أخذ أي جزء من العنصر: فقيمة جزء من العنصر i يزن w هي values[i] × w / weights[i].

اكتب دالة باسم fractionalKnapsack تُعيد أكبر قيمة إجمالية يمكن للحقيبة حملها، مقربةً إلى الأسفل إلى أقرب عدد صحيح.

الدالة

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: قيمة كل عنصر
weightsinteger-array: وزن كل عنصر
capacityinteger: أكبر وزن يمكن للحقيبة أن تحمله
تُرجعinteger: أكبر قيمة إجمالية تتسع لها الحقيبة، مع التقريب إلى الأسفل

القيود

1 ≤ n ≤ 5000، حيث n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

أمثلة

المدخلات: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
المخرجات: 151
الشرح: تبلغ قيمة الوحدات من العناصر لكل وحدة وزن 5 و3 و6 و2.5. يُؤخذ العنصران 2 و0 كاملين بقيمة 70، ويتبقى مكان لـ27، وتضيف 27 وحدة من وحدات العنصر 1 البالغ عددها 30 قيمة 81، ليصبح المجموع 151.

المدخلات: values = [10, 7]weights = [4, 3]capacity = 5
المخرجات: 12
الشرح: تبلغ قيمة الوحدة من العنصر 0 مقدار 2.5، ومن العنصر 1 نحو 2.33، لذا يُؤخذ العنصر 0 كاملًا بقيمة 10. وتضيف وحدة واحدة من وحدات العنصر 1 الثلاث 7 / 3، ويُقرَّب 12 وثلث إلى الأسفل ليصبح 12.

سؤال إضافي

هل يمكنك إيجاد الإجابة في زمن O(n)، دون فرز جميع العناصر؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

لأنه يمكنك تقسيم العناصر، فالمسألة جشعة، بخلاف مسألة حقيبة الظهر 0/1: يجب أن تأتي كل وحدة وزن من العنصر ذي أعلى قيمة لكل وحدة وزن متبقية. رتّب العناصر حسب هذه الكثافة واملأ الحقيبة بالترتيب. قارن الكثافات بالضرب التبادلي، وقرّب إلى الأسفل العنصر الذي تقسّمه فقط، حتى لا تُخزَّن أي كسور.

اختر العنصر الأعلى كثافةً في كل جولة

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

املأ الحقيبة بدءًا من العنصر الأعلى كثافةً، ثم الأقل كثافةً: خذ العنصر كاملًا إذا كان يتسع، وإلا فخذ الجزء الذي يملأ الحقيبة وتوقف. اعثر على العنصر غير المستخدم الأعلى كثافةً بمسحها جميعًا، ومقارنة values[i] × weights[j] مع values[j] × weights[i] بدلًا من القسمة. مع الأوزان الموجبة، يكون الاختبار مكافئًا، ويبقى كلا الناتجين أقل من أو مساويًا لـ 10^8.

البدء بالعناصر الأعلى كثافةً هو الأفضل: إذا احتوى الحمل على وزن من عنصر أقل كثافةً بينما لم يُضَف عنصر أعلى كثافةً بالكامل، فإن استبدال ذلك الوزن بالعنصر الأعلى كثافةً لا يمكن أن يقلل القيمة. واصل الاستبدال، وستصل إلى الحمل الذي اختيرت عناصره بترتيب تنازلي حسب الكثافة.

في كل واحدة من الجولات التي يصل عددها إلى n، امسح العناصر غير المستخدمة، أي نحو n²/2 = 12.5 مليون مقارنة عندما تكون n = 5000.

الخوارزمية

علِّم كل عنصر بأنه غير مستخدم، واضبط room = capacity وtotal = 0.
ما دامت هناك مساحة، افحص العناصر غير المستخدمة بحثًا عن العنصر الأعلى كثافة، بمقارنة الكثافات عن طريق الضرب التبادلي.
إذا لم يتبقَّ أي عنصر، فتوقف. وإلا فعلِّم ذلك العنصر بأنه مستخدم.
إذا كان يتسع، فأضف قيمته إلى total واطرح وزنه من room. وإذا لم يتسع، فأضف values[i] × room / weights[i] باستخدام القسمة الصحيحة، ثم توقف.
أعِد total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

رتّب حسب القيمة لكل وحدة وزن

الفكرة

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

خذ العناصر كاملةً ما دامت تتسع. أول عنصر لا يتسع هو الوحيد الذي تقسّمه: إذ يضيف values[i] × room / weights[i]، والقسمة الصحيحة تقرّب الناتج إلى الأسفل. كل ما يسبقه عدد صحيح، لذا فإن تقريب هذا الحد وحده يعطي الإجابة الدقيقة. تستغرق عملية الترتيب O(n log n)، والمسح O(n).

الخوارزمية

أنشئ قائمة بفهرس كل عنصر، ورتّبها بدءًا من العنصر ذي أعلى كثافة باستخدام مقارنة بالضرب التبادلي.
عيّن room = capacity وtotal = 0.
لكل عنصر بهذا الترتيب، إذا كان weights[i] ≤ room، فأضف قيمته واطرح وزنه من room.
وإلا، فأضف values[i] × room / weights[i] باستخدام القسمة الصحيحة، ثم توقّف.
أعِد total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

أخطاء شائعة وحالات حدّية

الترتيب حسب القيمة أو الوزن فقط. في المثال الأول، العنصر الذي تبلغ قيمته 90 يحتل المرتبة الثالثة فقط من حيث الكثافة؛ وأخذه أولًا يترك مساحة لنصف العنصر الذي تبلغ قيمته 50، فيكون الناتج 115 بدلًا من 151.
القسمة قبل الضرب. عندما تكون القيمة 13 والوزن 7 والمساحة المتاحة 3، فإن 13 / 7 * 3 في الحساب بالأعداد الصحيحة يعطي 3، بينما يعطي 13 * 3 / 7 الناتج الصحيح 5.
توقّع اقتطاع عنصر في كل مرة. في المثال الثالث، تتسع المساحة لكل العناصر، والإجابة هي مجموع القيم كلها، أي 13.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة الحقيبة الجزئية؟

ترتيب العناصر حسب القيمة لكل وزن يستغرق O(n log n)، ويُجرى الملء في مرور واحد، لذا يكون الإجمالي O(n log n) مع مساحة O(n) للترتيب. يستغرق البحث عن العنصر الأعلى كثافةً في كل جولة O(n²).

لماذا تنجح الخوارزمية الجشعة مع مشكلة حقيبة الظهر الكسرية، لكنها لا تنجح مع مشكلة حقيبة الظهر 0/1؟

يتيح لك التجزئة استبدال وزن عنصر أقل كثافة بوزن عنصر أعلى كثافة. ومن دون التجزئة، قد يترك العنصر عالي الكثافة مساحة لا يملؤها أي شيء آخر. مع القيم 8، 11، 15، والأوزان 2، 3، 4 والسعة 7، يختار أسلوب الأعلى كثافة أولًا الأوزان 2 و4 ليكون المجموع 23، بينما تعطي الأوزان 3 و4 المجموع 26. يتطلب الإصدار 0/1 البرمجة الديناميكية.

كيف تحل مشكلة حقيبة الظهر الكسرية دون استخدام أعداد الفاصلة العائمة؟

مع الأوزان الموجبة، يكون الاختبار a / b > c / d مكافئًا للاختبار a × d > c × b، لذا قارِن الكثافات بالضرب التبادلي. أفضل قيمة هي عدد صحيح مضافًا إليه كسر واحد، values[i] × room / weights[i] للعنصر الذي يُؤخذ جزء منه، لذا فإن قسمة صحيحة واحدة تعطي الإجابة المقربة إلى الأسفل بدقة.

def fractionalKnapsack(values, weights, capacity):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

الإخراج المتوقع