നിർദ്ദിഷ്ട വ്യത്യാസമുള്ള ജോഡികളുടെ പരമാവധി തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് Coursera ദില്ലി ഫോർകൈറ്റുകൾ സ്നാപ്ഡേൽ
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

“നിർദ്ദിഷ്ട വ്യത്യാസമുള്ള ജോഡികളുടെ പരമാവധി തുക” എന്ന പ്രശ്‌നം നിങ്ങൾക്ക് ഒരു ശ്രേണി നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യകൾ ഒരു സംഖ്യ കെ. എന്നിട്ട് സ്വതന്ത്ര ജോഡികളുടെ പരമാവധി തുക കണ്ടെത്താൻ ഞങ്ങളോട് ആവശ്യപ്പെടും. K- നേക്കാൾ കുറഞ്ഞ വ്യത്യാസമുണ്ടെങ്കിൽ നമുക്ക് രണ്ട് പൂർണ്ണസംഖ്യകൾ ജോടിയാക്കാം. അതിനാൽ, അത്തരം x ജോഡികളുടെ പരമാവധി തുക 2x സംഖ്യകളായി കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

നിർദ്ദിഷ്ട വ്യത്യാസമുള്ള ജോഡികളുടെ പരമാവധി തുക

42, 43, 4, 5, 6, 12
96

വിശദീകരണം

ഞങ്ങൾ 42, 43, 5, 6 എന്നിവ തിരഞ്ഞെടുക്കുന്നു. ഞങ്ങൾക്ക് 4, 5, 6 എന്നിവയിൽ ഓപ്ഷനുകൾ ഉണ്ടായിരുന്നു. അതിനാൽ, അവയ്ക്കിടയിൽ പരമാവധി മൂല്യം ഞങ്ങൾ എടുക്കുന്നു = 96.

സമീപനം

ന്റെ ചില ഘടകങ്ങൾ‌ ജോടിയാക്കിയാൽ‌ നേടാൻ‌ കഴിയുന്ന പരമാവധി തുക കണ്ടെത്താൻ‌ പ്രശ്നം നമ്മോട് ആവശ്യപ്പെടുന്നു ശ്രേണി. മൂലകങ്ങൾക്ക് കെ യേക്കാൾ കുറവായിരിക്കണം എന്ന നിർബന്ധിത വ്യവസ്ഥയിൽ നമുക്ക് ഘടകങ്ങളെ ജോടിയാക്കാൻ കഴിയും. പ്രശ്നം പരിഹരിക്കുന്നതിന് മുമ്പ്, ഞങ്ങൾ അടുക്കുക ശ്രേണി. ഇതുവഴി ഞങ്ങൾ ഞങ്ങളുടെ തിരയൽ ഇടം വെട്ടിച്ചുരുക്കുന്നു. ഞങ്ങൾക്ക് അടുക്കിയിട്ടില്ലാത്ത ഒരു അറേ ഉണ്ടായിരുന്നുവെന്ന് പരിഗണിക്കുക. ഒരു മൂലകം ജോടിയാക്കുന്നതിനായി എല്ലാ ഘടകങ്ങളും സഞ്ചരിക്കേണ്ടതുണ്ട്. എന്നാൽ അടുക്കിയതിനുശേഷം ഏറ്റവും വലിയ മൂലകം അതിന് മുമ്പുള്ള മൂലകം മാത്രമാണെന്ന് നമുക്കറിയാം. അതിനാൽ ഈ അവസ്ഥ തൃപ്‌തികരമാണോയെന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു.

അവസ്ഥ തൃപ്‌തികരമാണെങ്കിൽ, മുമ്പത്തേതും നിലവിലുള്ളതുമായ ഘടകം ഞങ്ങൾ ജോടിയാക്കുകയും അവസാന രണ്ടാമത്തെ ഘടകം വരെ (നിലവിലെ ഘടകത്തിൽ നിന്ന്) പ്രശ്‌നത്തിനുള്ള ഫലം ചേർക്കുകയും ചെയ്യുന്നു. എന്നാൽ അവസ്ഥ തൃപ്തികരമല്ലെങ്കിൽ. ഞങ്ങൾ ജോടിയാക്കൽ ഉപേക്ഷിക്കുന്നു, ഫലം മുമ്പത്തെ ഘടകം വരെ തുല്യമായിരിക്കും. കൂടുതൽ ly പചാരികമായി, ഫലം [i] = ഫലം [i-2] + ഇൻപുട്ട് [i] + ഇൻപുട്ട് [i-2], ജോടിയാക്കൽ മറ്റുവിധത്തിൽ ചെയ്താൽ ഫലം [i] = ഫലം [i-1]. ഇവിടെ ഈ ഫല ശ്രേണി ഞങ്ങളുടെതാണ് DP അറേ കാരണം ചെറിയ ഉപപ്രശ്നങ്ങളുടെ ഫലം ഞങ്ങൾ സംഭരിക്കുന്നു. ചുവടെയുള്ള ഡിപിയിൽ ചെയ്യുന്നതുപോലെ യഥാർത്ഥ പ്രശ്‌നത്തിന്റെ ഫലം കണ്ടെത്തുന്നതിന് ഈ ചെറിയ ഉപപ്രൊബ്ലെമുകളുടെ ഫലം ഞങ്ങൾ സംയോജിപ്പിക്കുന്നു.

കോഡ്

നിർദ്ദിഷ്ട വ്യത്യാസമുള്ള ജോഡികളുടെ പരമാവധി തുക കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

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

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

നിർദ്ദിഷ്ട വ്യത്യാസമുള്ള ജോഡികളുടെ പരമാവധി തുക കണ്ടെത്താൻ ജാവ കോഡ്

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത 

O (NlogN), കാരണം ഞങ്ങൾ തുടക്കത്തിൽ അറേ അടുക്കിയിരുന്നു. ലയനം അടുക്കുന്നതിനും മറ്റ് തരംതിരിക്കൽ അൽ‌ഗോരിതംസിനും O (NlogN) ലെ ശ്രേണി ക്രമപ്പെടുത്താൻ‌ കഴിയും. ഞങ്ങൾക്ക് ഒരു അടുക്കിയ ഇൻപുട്ട് നൽകിയിരുന്നെങ്കിൽ, O (N) സമയത്തിനുള്ളിൽ ഞങ്ങൾക്ക് പ്രശ്നം പരിഹരിക്കാമായിരുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), അറേ അടുക്കുന്നതിന് ഈ ഇടം ആവശ്യമാണ്. ഞങ്ങൾ‌ ഡി‌പി അറേ ചെയ്‌തില്ലെങ്കിലും ഡി‌പി പട്ടികയ്‌ക്കായി സമാന ഇൻ‌പുട്ട് അറേ ഉപയോഗിക്കുമായിരുന്നു. ഈ പരിഹാരത്തിന് ഇപ്പോഴും സമാന സ്ഥല സങ്കീർണ്ണതയുണ്ട്, കാരണം ഈ സ്ഥലം അടുക്കുന്നതിന് ആവശ്യമാണ്.