0/1 إصلاح مشكلة حقيبة الظهر باستخدام مثال البرمجة الديناميكية

ما هي مشكلة الحقيبة؟

استخدم مشكلة الحقيبة هي مسألة كلاسيكية في مجال التحسين التوافقي. متجر سوبر ماركت n عدد الحزم (n ≤ 100). حزمة i وزنها W[i] ≤ 100 وقيمتها V[i] ≤ 100. لا يستطيع اللص حمل وزن يتجاوز السعة M (M ≤ 100). ما هي الطرود التي يجب على اللص أخذها لزيادة القيمة الإجمالية إلى أقصى حد؟

الإدخال:

• الحد الأقصى للوزن M وعدد الطرود n.
• صفيف الوزن W[i] والقيمة المقابلة V[i].

الإخراج:

• أقصى قيمة إجمالية يمكن الحصول عليها ضمن السعة المتاحة.
• مجموعة الطرود التي يجب على اللص أخذها بالضبط.

تنقسم خوارزمية حقيبة الظهر إلى نوعين معروفين جيداً:

• مشكلة حقيبة الظهر 0/1 تم حل المشكلة باستخدام البرمجة الديناميكية. يتم أخذ كل حزمة كاملة أو تركها - لا توجد أجزاء جزئية ولا تكرارات.
• مشكلة الحقيبة الكسرية تم حل المشكلة باستراتيجية جشعة. هنا يمكنك أخذ جزء من أي حزمة لملء السعة المتبقية.

كيفية حل مشكلة الحقيبة باستخدام البرمجة الديناميكية مع المثال

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

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

حل مشكلة الحقيبة باستخدام البرمجة الديناميكية

لتصميم حل برمجة ديناميكية، اتبع الخطوات الأربع التالية:

• ابدأ بحل أصغر المسائل الفرعية أولاً.
• استنتج علاقة تكرارية تبني حلاً لمسألة فرعية من مسائل أصغر.
• قم بتخزين إجابات المسائل الفرعية في جدول يتم حسابه من الأسفل إلى الأعلى باستخدام التكرار.
• قم بتجميع الإجابة النهائية من الجدول المكتمل.

تحليل مشكلة حقيبة الظهر 0/1

تعتمد القيمة المثلى على عاملين مستقلين:

1. كم عدد الطرود التي لا تزال قيد الدراسة؟
2. الوزن المتبقي الذي لا يزال بإمكان حقيبة الظهر تخزينه.

بما أن دالة الهدف تعتمد على كميتين، فإن جدول الخيارات يجب أن يكون ثنائي الأبعاد. ليكن B[i][j] لنفترض القيمة القصوى عند الاختيار بين الحزم {1، ...، i} ذات حد الوزن j.

• الجواب النهائي هو B[n][M]، أفضل قيمة إجمالية عبر جميع الحزم n ذات السعة M.
• الوزن الإجمالي المحدد يكون دائمًا محدودًا بالسعة الحالية: B[i][j] ≤ j.

مثال: إذا كان B[4][10] = 8، فإن أفضل وزن إجمالي من أول أربع عبوات تحت سعة 10 هو 8. يمكن تخطي بعض هذه العبوات الأربع.

صيغة لحساب B[i][j]

• W[i], V[i] يمثل وزن وقيمة الحزمة i، حيث i ينتمي إلى {1، …، n}.
• M هو أقصى وزن يمكن أن تحمله حقيبة الظهر.

الحالة الأساسية مع حزمة واحدة: لكل سعة j ≥ W[1]:

B[1][j] = W[1]

في الحالة العامة، قرر ما إذا كان سيتم تضمين الحزمة i ضمن السعة j:

• إذا كانت الحزمة i تخطي، B[i][j] يساوي أفضل قيمة باستخدام الحزم {1، …، i-1} في ظل السعة j:

B[i][j] = B[i - 1][j]

• إذا كانت الحزمة i اتخذت (مسموح به فقط عندما يكون W[i] ≤ j)، B[i][j] يساوي V[i] بالإضافة إلى أفضل قيمة من الحزم {1، …، i-1} ضمن السعة j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

اختر المرشح الأكبر من بين المرشحين.

أساس البرمجة الديناميكية

يؤدي الجمع بين الحالتين إلى الحصول على التكرار الكامل:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

الحالة الأساسية هي B[0][j] = 0 لكل j، لأن الحزم الصفرية تعطي قيمة صفرية بغض النظر عن السعة.

احسب جدول الخيارات

قم ببناء الجدول B باستخدام التكرار. بمجرد ملء الجدول B، يتم استخدام نفس الجدول لتشغيل... tracإعادة بناء الحزم المختارة. يحتوي الجدول ب على ن + ١ صفًا و م + ١ عمودًا:

• الصف 0 هو الحالة الأساسية، وهو مملوء بالأصفار.
• استخدم الصف 0 لحساب الصف 1، والصف 1 لحساب الصف 2، واستمر حتى يكتمل الصف n.

جدول الخيارات

Trace

بمجرد اكتمال الجزء "ب"، ركز على B[n][M]، القيمة الإجمالية المثلى عبر جميع الحزم n ذات السعة M.

• If B[n][M] = B[n-1][M]لم يتم تحديد الحزمة رقم n، لذا تابع tracing from B[n-1][M].
• If B[n][M] ≠ B[n-1][M]تم اختيار الحزمة رقم n، لذا تابع tracing from B[n-1][M – W[n]].

كرر العملية حتى تصل إلى الصف 0 من الجدول.

خوارزمية للبحث في جدول الخيارات للعثور على الحزم المحددة

ملاحظة: كلما B[i][j] = B[i-1][j]لم يتم تحديد الحزمة i. القيمة B[n][M] هي القيمة الإجمالية المثلى المعبأة في حقيبة الظهر.

خطوات ل tracاستلام الحزم المختارة:

• الخطوة 1 : ابدأ من i = n، j = M.
• الخطوة 2 : امسح العمود j من الأسفل إلى الأعلى حتى تجد الصف i حيث B[i][j] > B[i-1][j]. حدد الحزمة i على أنها محددة. Select[i] = true.
• الخطوة 3 : قم بتحديث j = j – W[i]. إذا كانت j > 0، فارجع إلى الخطوة 2، وإلا فانتقل إلى الخطوة 4.
• الخطوة 4 : اطبع كل حزمة تم تحديدها.

Java Code

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

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

وظيفة knapsackDyProg() في Java

شرح الكود:

1. تخصيص الجدول B[][] وقم بتهيئة كل خلية إلى الصفر.
2. املأ B[][] من الأسفل إلى الأعلى باستخدام التكرار من القسم السابق.
3. ابدأ كل خلية بقيمة "تجاوز الحزمة رقم i" B[i-1][j].
4. إذا كان اختيار الحزمة i ممكناً ويعطي قيمة أفضل بشكل واضح، فاستبدل الخلية.
5. Trace أعد العناصر المحددة من الصف n إلى الصف 0.
6. عند اختيار الحزمة رقم n، يتم تقليل السعة المتبقية بمقدار W[n-1].

ملاحظة تصحيحية: المعلمة المعدلة في المقتطف الأصلي M أثناء القراءة B[n][M]يستخدم الإصدار الأكثر أمانًا أعلاه مؤشرًا منفصلاً j ل trace.

استخدم Java يقوم برنامج التشغيل بتشغيل الخوارزمية على مثالين عمليين:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

الناتج الخاص بالمثال الأول:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

الناتج الخاص بالمثال الثاني:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

تعقيد الوقت والمساحة لحقيبة الظهر 0/1

• التعقيد الزمني: O(n · M) — تقوم الحلقتان المتداخلتان بمسح n عنصرًا عبر M+1 حالة سعة.
• تعقيد المساحة: O(n · M) للجدول الكامل، قابلة للاختزال إلى O(M) عن طريق الاحتفاظping الصف السابق فقط عندما tracلا حاجة للرد الإلكتروني.

وقت التشغيل هو متعدد الحدود الزائف: متعدد الحدود في قيمة M ولكنه أسي في البتات المستخدمة لترميز M. ولهذا السبب تظل مسألة حقيبة الظهر 0/1 مسألة صعبة من نوع NP على الرغم من أن البرمجة الديناميكية فعالة من الناحية العملية.

تطبيقات مسألة حقيبة الظهر 0/1

• تحميل البضائع، وتعبئة الحاويات، وفرز البضائع في المستودعات ضمن حدود الوزن المسموح بها.
• تخصيص الميزانية عبر مشاريع الاستثمار ذات التكلفة الثابتة والعائد المتوقع.
• مشاكل تقطيع المخزون في التصنيع التي لا تسمح بتقسيم القطع الفردية.
• أنظمة التشفير مثل Merkle-Hellman التي تعتمد على صلابة حقيبة الظهر.
• جدولة الموارد المحدودة في الحوسبة السحابية وتوزيع مهام وحدة المعالجة المركزية.
• اختيار الميزات في التعلم الآلي في ظل ميزانية ميزات ثابتة.

الأسئلة الشائعة