مشكلة تقسيم الرسام  


مستوى الصعوبة الثابت
كثيرا ما يطلب في CodeNation جوجل
بحث ثنائي فرق تسد البرمجة الديناميكية البحث

المشكلة بيان  

تنص مشكلة تقسيم الرسام على أن لدينا بعض الأسوار ولدينا بعض الرسامين. نريد تقليل وقت طلاء جميع الأسوار بواسطة الرسامين. هناك قيود على ترتيب طلاء الأسوار من قبل الرسامين. ضع في اعتبارك أن لدينا عددًا من الرسامين ، ثم يمكن للرسام ذي الفهرس "i" رسم الأسوار بترتيب مستمر فقط.

هذا يعني أن الرسام الأول سيرسم بعض الأسوار. ثم يرسم الرسام الثاني بعض الأسوار. الشيء نفسه ينطبق على جميع الرسامين. قد يحدث هذا حتى أن بعض الرسامين لا يحصلون على سياج لطلائه.

مثال  

مشكلة تقسيم الرسامدبوس

Size of fence : 10 40 40 10 
Time of painting a unit length of fence : 1
Number of Painters : 2
50

التفسير: سنخصص السياج 1 و 2 للرسام الأول و 3 ، 4 للرسام الثاني. إذا كنا سنخصص سياجًا واحدًا للرسام الأول و 1 و 2 و 3 للرسام الثاني. ثم يأخذ الرسام الأول الوقت = 4 ، والثاني يأخذ الوقت = 10. الحد الأقصى للوقت الذي يستغرقه جميع الرسامين هو الوقت الإجمالي الذي يستغرقه طلاء السياج. هذا لأن جميع الرسامين يبدؤون الرسم في نفس الوقت t = 90. وبالتالي ، فإن أي طريقة أخرى غير ذلك ستؤدي إلى نتائج أسوأ.

Size of fence : 1 100 
Time of painting a unit length of fence : 1 
Number of Painters : 2
100

التفسير: سنخصص السور 1 للرسام الأول و 2 للرسام الثاني. حيث أن الوقت الإجمالي يساوي الحد الأقصى للوقت الذي يستغرقه أي من الرسامين. وبالتالي ، يكون الناتج 100.

نهج مشكلة تقسيم الرسام  

سوف نستخدم البرمجة الديناميكية لحل هذه المشكلة. هنا ، سنستخدم أيضًا ملف البرمجة الديناميكية تقنية (مجموع البادئة) لأخذ مجموع الوقت في تعقيد الوقت O (1). أولاً ، سنحل المشكلة لرسام واحد. ثم سنحل بطريقة تصاعدية لعدد الرسامين = 2 ، 3 ، 4 ، ... ن. لحل مشكلة الرسام ، سنجد الوقت الذي يستغرقه الرسام لطلاء السياج من k إلى j. هنا ، اعتبرنا أن الرسام سوف يرسم السياج من k إلى j ويتم رسم الأسوار من 1 إلى (k-1) بواسطة الرسامين (i-1). يجب أن تكون الإجابة عن هذه المشكلة الفرعية هي الحد الأقصى للوقت الذي يستغرقه أي من الرسامين (i-1) أو الرسام. بهذه الطريقة ، نستمر في حل المشكلات الفرعية الأصغر. بعد ذلك ، بدمج نتيجة هذه المشكلات الفرعية الأصغر سنحل مشكلتنا الأولية (مشكلة تقسيم الرسام).

رمز  

كود C ++ لمشكلة تقسيم الرسام

#include <bits/stdc++.h>
using namespace std;

long long int solvePaintersPartitionProblem(long long int numberOfPainters, long long int timePerUnit, vector<long long int>& fenceSize){
    int numberOfFences = fenceSize.size();
    if(numberOfFences == 0)return 0;

    vector<long long int> pref(numberOfFences); // stores the prefix sum for faster sum calculation over the range

    pref[0] = (fenceSize[0] * timePerUnit);
    for(int i=1;i<numberOfFences;i++) {
        pref[i] = (fenceSize[i] * timePerUnit);
        pref[i] = (pref[i] + pref[i-1]);
    }

    long long int dp[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
    for(int i=0;i<numberOfPainters;i++){
        for(int j=0;j<numberOfFences;j++)
            dp[i][j] = LONG_MAX;
    }

    // Filling the values for first painter
    for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];

    // Now solving for painters 2, 3, 4......n
    for(int i=1;i<numberOfPainters;i++){
        for(int j=i;j<numberOfFences;j++){
            for(int k=i;k<=j;k++){
                long long int timeTakenForithPainter = pref[j] - pref[k-1];
                dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], timeTakenForithPainter));
            }
        }
    }

    if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
    return dp[numberOfPainters-1][numberOfFences-1];
}


int main(){
    int t;cin>>t;
    while(t--){
        long long int numberOfPainters, numberOfFences, timePerUnit;
        cin>>numberOfPainters>>timePerUnit>>numberOfFences;
        vector<long long int> fenceSize(numberOfFences);
        for(int i=0;i<numberOfFences;i++) cin>>fenceSize[i];
        long long int ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, fenceSize);
        cout<<ans<<endl;
    }
}
2

2 5 2 // number of painters, time taken paint a unit length of fence and number of fences

1 10  // fences size

10 1 4

1 8 11 3
50 
11

كود جافا لمشكلة تقسيم الرسام

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static long solvePaintersPartitionProblem(int numberOfPainters, long timePerUnit, int numberOfFences, long fenceSize[]){
        if(numberOfFences == 0)return 0;
        long pref[] = new long[numberOfFences]; // stores the prefix sum for faster sum calculation over the range
        pref[0] = (fenceSize[0] * timePerUnit);
        for(int i=1;i<numberOfFences;i++) {
            pref[i] = (fenceSize[i] * timePerUnit);
            pref[i] = (pref[i] + pref[i-1]);
        }
    
        long dp[][] = new long[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
        for(int i=0;i<numberOfPainters;i++){
            for(int j=0;j<numberOfFences;j++)
                dp[i][j] = Long.MAX_VALUE;
        }
    
        // Filling the values for first painter
        for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];
    
        // Now solving for painters 2, 3, 4......n
        for(int i=1;i<numberOfPainters;i++){
            for(int j=i;j<numberOfFences;j++){
                for(int k=i;k<=j;k++){
                    long timeTakenForithPainter = pref[j] - pref[k-1];
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k-1], timeTakenForithPainter));
                }
            }
        }
        if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
        return dp[numberOfPainters-1][numberOfFences-1];
    }


    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
  int t = sc.nextInt();
        while(t-- > 0){
            int numberOfPainters = sc.nextInt();
            long timePerUnit = sc.nextLong();
            int numberOfFences = sc.nextInt();
            long fenceSize[] = new long[numberOfFences];
            for(int i=0;i<numberOfFences;i++) fenceSize[i] = sc.nextLong();
            long ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, numberOfFences, fenceSize);
            System.out.println(ans);
        }
    }
}
2

2 5 2// number of painters, time taken paint a unit length of fence and number of fences 

1 10 // fences size

10 1 4

1 8 11 3
50 
11

تحليل التعقيد  

تعقيد الوقت: O (N * M ^ 2)

حيث N = عدد الرسامين 

M = عدد الأسوار ، نظرًا لأننا هنا نستخدم مجموع البادئة لإيجاد الوقت الذي يقضيه الرسام ، فقد قللنا من تعقيد الوقت.

تعمل الحلقة الأولى على عدد من الرسامين ، وتعمل الحلقات المتداخلة على عدد الأسوار. إذا كانت N = M ، فإن تعقيد الوقت: O (N ^ 3) لمشكلة تقسيم الرسام.

تعقيد الفضاء: O (N * M)

حيث N = عدد الرسامين 

M = عدد الأسوار ، لأن لدينا مجموعة ثنائية الأبعاد DP ذات أبعاد N * M. وبالتالي لدينا حل تعقيد مساحة متعدد الحدود لمشكلة تقسيم الرسام.

انظر أيضا
ابحث عن أي عنصر من العناصر المكررة المتعددة في مجموعة القراءة فقط