پینٹر کی تقسیم کا مسئلہ


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے کوڈ نیشن گوگل
ثنائی تلاش تقسیم اور فتح متحرک پروگرامنگ تلاش

مسئلہ یہ بیان

پینٹر کی تقسیم کا مسئلہ بیان کرتا ہے کہ ہمارے پاس کچھ باڑ ہیں اور ہمارے پاس کچھ پینٹر ہیں۔ ہم پینٹرز کے ذریعہ تمام باڑوں کو پینٹنگ کرنے کے وقت کو کم سے کم کرنا چاہتے ہیں۔ مصوروں کے ذریعہ باڑ پینٹنگ کے آرڈر کا پابند ہے۔ غور کریں کہ ہمارے پاس ن پینٹر ہیں ، پھر انڈیکس '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 لیتا ہے ، اور دوسرا وقت 90 = 0 لیتا ہے۔ تمام مصوروں نے زیادہ سے زیادہ وقت باڑ کو رنگنے میں لیا ہے۔ اس کی وجہ یہ ہے کہ تمام مصور ایک ہی وقت میں ٹی پینٹنگ شروع کرتے ہیں = = اسی طرح ، اس کے علاوہ کوئی دوسرا راستہ بدتر نتائج کا نتیجہ نکلے گا۔

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

وضاحت: ہم پہلے پینٹر کو باڑ 1 اور دوسرے پینٹر کو 2 لگائیں گے۔ چونکہ کل وقت کسی بھی مصور کے ل by زیادہ سے زیادہ وقت کے برابر ہے۔ اس طرح ، پیداوار 100 ہے۔

پینٹر کی تقسیم کے مسئلے کے لئے نقطہ نظر

ہم استعمال کریں گے متحرک پروگرامنگ اس مسئلے کو حل کرنے کے ل. یہاں ، ہم ایک بہت عمدہ تعریف شدہ بھی استعمال کریں گے متحرک پروگرامنگ او (1) وقت کی پیچیدگی میں وقت کا مجموعہ لینے کے لئے تکنیک (سابقہ ​​رقم)۔ سب سے پہلے ، ہم ایک پینٹر کے لئے مسئلہ حل کریں گے۔ اس کے بعد ہم مصوروں کی تعداد = 2 ، 3 ، 4 ،… این کے اختتامی انداز میں حل کریں گے۔ ایک آٹھ پینٹر کے مسئلے کو حل کرنے کے ل we ، ہم باٹ پی سے جے تک پینٹ کرنے کے لئے آٹ پینٹر کے ذریعہ لیا ہوا وقت تلاش کریں گے۔ یہاں ، ہم نے یہ خیال کیا ہے کہ آیتھ پینٹر باڑ 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 = مصوروں کی تعداد 

ایم = باڑوں کی تعداد ، چونکہ ہم یہاں آٹ پینٹر کے ذریعہ گزارے گئے وقت کو تلاش کرنے کے لئے ماقبل کا استعمال کر رہے ہیں اس لئے ہم نے وقت کی پیچیدگی کو کم کردیا ہے۔

پہلا لوپ پینٹروں کی تعداد سے زیادہ چلتا ہے ، اور نیسڈڈ لوپ باڑوں کی تعداد سے زیادہ چلتے ہیں۔ اگر N = M ، وقت کی پیچیدگی: O (N ^ 3) پینٹر کی تقسیم کی پریشانی کے لئے۔

خلائی پیچیدگی: O (N * M)

جہاں N = مصوروں کی تعداد 

M = باڑوں کی تعداد ، کیونکہ ہمارے پاس طول و عرض کی 2D DP صف ہے N * M۔ اس طرح ہمارے پاس پینٹر کی تقسیم کی پریشانی کے لئے ایک کثیرالقوی خلائی پیچیدگی کا حل ہے۔