فهم مشكلة الحقيبة (0/1 Knapsack) مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

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

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

المدخلات والمخرجات:

• المدخلات: عدد العناصر، والوزن والقيمة لكل عنصر، والوزن الأقصى للحقيبة.
• المخرجات: القيمة القصوى الممكنة مع عدم تجاوز الوزن الأقصى للحقيبة.

2. شرح تعليمي للحل

مفهوم مشكلة الحقيبة:

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

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

تعقيد الوقت:

• O(n * W)، حيث n هو عدد العناصر و W هو الوزن الأقصى للحقيبة.

تعقيد المساحة:

• O(n * W) لتخزين جدول البرمجة الديناميكية.

3. الحل في Python

def knapsack(W, wt, val, n):
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    # بناء جدول البرمجة الديناميكية
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][W]

# استخدام المثال
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print("القيمة القصوى الممكنة هي:", knapsack(W, wt, val, n))

4. الحل في Java

public class Knapsack {

    // دالة لإيجاد القيمة القصوى الممكنة
    static int knapSack(int W, int wt[], int val[], int n) {
        int dp[][] = new int[n + 1][W + 1];

        // بناء جدول البرمجة الديناميكية
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    dp[i][w] = 0;
                else if (wt[i - 1] <= w)
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                else
                    dp[i][w] = dp[i - 1][w];
            }
        }
        return dp[n][W];
    }

    // دالة القيادة لاختبار ما سبق
    public static void main(String args[]) {
        int val[] = new int[]{60, 100, 120};
        int wt[] = new int[]{10, 20, 30};
        int W = 50;
        int n = val.length;
        System.out.println("القيمة القصوى الممكنة هي: " + knapSack(W, wt, val, n));
    }
}

5. الحل في C

#include <stdio.h>

// دالة لإيجاد القيمة القصوى الممكنة
int knapSack(int W, int wt[], int val[], int n) {
    int dp[n + 1][W + 1];

    // بناء جدول البرمجة الديناميكية
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (wt[i - 1] <= w)
                dp[i][w] = (val[i - 1] + dp[i - 1][w - wt[i - 1]] > dp[i - 1][w]) ? val[i - 1] + dp[i - 1][w - wt[i - 1]] : dp[i - 1][w];
            else
                dp[i][w] = dp[i - 1][w];
        }
    }
    return dp[n][W];
}

// دالة القيادة لاختبار ما سبق
int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    printf("القيمة القصوى الممكنة هي: %d\n", knapSack(W, wt, val, n));
    return 0;
}

SEO