Занҷири дарозии максималии ҷуфтро чоп кунед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon
Барномарезии динамикӣ

Изҳороти мушкилот

Масъалаи "Занҷири дарозии максималии ҷуфтҳоро чоп кунед" гуфта шудааст, ки ба шумо якчанд ҷуфт рақамҳо дода мешаванд. Дода мешавад, ки дар ҳар як ҷуфт, рақами аввал аз рақами дуюм хурдтар аст. Акнун ба шумо лозим аст, ки занҷири дарозтаринро пайдо кунед, ки шумораи дуюми ҷуфти қаблӣ (a, b) аз шумораи якуми ҷуфти баъд аз ҷуфти (c, d) хурдтар бошад (b <c).

мисол

(1, 10), (11, 25), (26, 35), (36, 50)
(1, 10), (11, 25), (26, 35), (36, 50)

Шарҳ

Мо ҳама ҷуфтҳоро интихоб кардем, зеро ҳамаи ҷуфтҳои додашуда шартро қонеъ карданд.

(1, 2), (10, 30), (5, 6), (15, 25), (17, 21)
(1, 2), (5, 6), (10, 30)

Шарҳ

Ҷуфти сеюм, ки мо интихоб кардем, аҳамият надорад. Мо метавонистем аз се ҷуфти боқимонда интихоб кунем, зеро ҳамаи онҳо шартро қонеъ карданд. Аммо мо аз се боқимонда ҳеҷ кадоме аз онҳоро интихоб карда наметавонем.

Усули чопи занҷири дарозии максималии ҷуфтҳо

Мушкилот аз мо талаб мекунад, ки занҷири дарозии максималии ҷуфтҳоро ёбем ва чоп кунем. Пас дарозии максималӣ дар ин ҷо чӣ маъно дорад? Дарозии максималӣ дар ин ҷо шумораи ҷуфтҳоро дар натиҷа нишон медиҳад. Пас, дар ниҳоят, мо бояд он ҷуфтҳоро ёбем, ки дарозии максималиро ташкил медиҳанд.

Мо аллакай муҳокима кардем ин мушкилот. Мушкиле, ки мо муҳокима кардем, аз мо хоҳиш кард, ки дарозии максималиро ёбем. Дар он ҷо мо роҳҳои гуногунро барои ҳалли мушкилот муҳокима кардем. Дар ин ҷо, дар ин қисми масъала, мо низ бояд чунин ҷуфтҳоро пайдо кунем. Мо масъаларо бо истифодаи барномасозии динамикӣ ҳал хоҳем кард, зеро ҳалли он бо истифодаи рекурсия аз мӯҳлат зиёд хоҳад буд. Муносибати такрорӣ ба муносибати LIS хеле монанд аст (пайдарпаии дарозтарин). Мо вектори векторҳо месозем. Ҳар як унсури ин вектори векторҳо ҷуфтҳоро нишон медиҳад, ки пайдарпаии дарозии максималиро ташкил медиҳанд, вақте ки мо ҳамеша унсури мувофиқи унсури ҷории вурудро интихоб мекунем.

Пас, муносибати такрорӣ ин аст

Занҷири дарозии максималии ҷуфтро чоп кунед

рамз

Коди C ++ барои чоп кардани занҷири дарозии ҷуфтҳо

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


void maxChainLength(vector<pair<int,int>> &input) 
{ 
    sort(input.begin(), input.end());
  
    int n = input.size();
    vector<vector<pair<int,int>>> dp(n); 
  	int mx = 0;
    // base case
    dp[0].push_back(input[0]); 
    for(int i=1;i<n;i++) 
    {
        for(int j=0;j<i;j++)
        {
            if ((input[j].second < input[i].first) && (dp[j].size() > dp[i].size())) // the condition must be satisfied 
                dp[i] = dp[j];
        } 
        dp[i].push_back(input[i]);
        if(dp[i].size() > dp[mx].size())
        	mx = i;
    }
    for(auto x: dp[mx])
    	cout<<"("<<x.first<<", "<<x.second<<") ";
} 

int main()
{ 
    vector<pair<int,int>> input = {{1, 2}, {10, 30}, {5, 6}, {15, 25}, {17, 21}};
    maxChainLength(input);
}
(1, 2) (5, 6) (10, 30)

Рамзи Java барои чоп кардани занҷири дарозии ҷуфтҳо

import java.util.*;

class Main{
    static void maxChainLength(ArrayList<ArrayList<Integer>> input)
    {
        Collections.sort(input, new Comparator<ArrayList<Integer>> () {
            @Override
            public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
                return a.get(0).compareTo(b.get(0));
            }
        });

        int n = input.size();
        ArrayList<ArrayList<ArrayList<Integer>>> dp = new ArrayList<ArrayList<ArrayList<Integer>>>();
        for(int i=0;i<n;i++)
            dp.add(new ArrayList<ArrayList<Integer>>());
        int mx = 0;
        // base case
        dp.get(0).add(input.get(0));
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(input.get(j).get(1) < input.get(i).get(0) && (dp.get(j).size() > dp.get(i).size())){
                    dp.set(i, new ArrayList<ArrayList<Integer>>(dp.get(j)));
                }
            }
            dp.get(i).add(input.get(i));
            if(dp.get(i).size() > dp.get(mx).size())
                mx = i;
        }
        for(ArrayList<Integer> x: dp.get(mx))
            System.out.print("("+x.get(0)+", "+x.get(1)+") ");
    }

    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> input = new ArrayList<ArrayList<Integer>>();
        input.add(new ArrayList(Arrays.asList(1, 2)));
        input.add(new ArrayList(Arrays.asList(10, 30)));
        input.add(new ArrayList(Arrays.asList(5, 6)));
        input.add(new ArrayList(Arrays.asList(15, 25)));
        input.add(new ArrayList(Arrays.asList(17, 21)));
        maxChainLength(input);
    }
}
(1, 2) (5, 6) (10, 30)

Таҳлили мураккабӣ

Мураккабии вақт

O (N ^ 2), зеро мушкилот ба мушкилоти ЛИС монанд аст. Ва дар ин масъала мо як ҳалқаи лонаеро барои ёфтани як ҷуфт занҷир истифода кардем, ки агар ҷуфти ҷориро илова кунем. Шарт қонеъ аст. Ҳамин тавр мураккабии вақт полиномия аст.

Мураккабии фазо

O (N ^ 2), мураккабии фазо низ полином аст, зеро мо вектори векторҳоро истифода кардем. Дар бадтарин ҳолат, вақте ки дарозии занҷир ба андозаи вуруд баробар аст. Он гоҳ вектори векторҳои мо ҷуфтҳои O (N ^ 2) доранд. Ҳамин тариқ, фазои зарурӣ низ бисёрҷабҳа мебошад.