A, b மற்றும் c நீளங்களின் அதிகபட்ச எண்ணிக்கை


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் கருப்பு பாறை ByteDance Citrix கூகிள் டெரடாட்டா கிழித்து
டைனமிக் புரோகிராமிங்

“A, b மற்றும் c நீளங்களின் அதிகபட்ச எண்ணிக்கையிலான பிரிவுகளின் சிக்கல்” உங்களுக்கு ஒரு நேர்மறையான முழு எண் N வழங்கப்பட்டதாகக் கூறுகிறது, மேலும் N ஐப் பயன்படுத்தி உருவாக்கக்கூடிய அதிகபட்ச நீளமான a, b மற்றும் c நீளங்களைக் கண்டுபிடிக்க வேண்டும்.

உதாரணமாக

A, b மற்றும் c நீளங்களின் அதிகபட்ச எண்ணிக்கை

N = 7
a = 5, b = 2, c = 3
3

விளக்கம்

இங்கே நாம் பேராசை அணுகுமுறையுடன் சென்றால், எல்லா பிரிவுகளையும் மிகச்சிறிய பிரிவுடன் (= 2) குறைக்க முயற்சிக்கிறோம். அளவு 1 இன் கடைசி பகுதியை எங்களால் உருவாக்க முடியாது. இவ்வாறு நீளம் 4 ஐ இரண்டு 2 நீளப் பிரிவுகளிலும் ஒரு 4 நீளப் பிரிவிலும் பிரிக்கிறோம்.

அணுகுமுறை

சிக்கல் எங்களுக்கு ஒரு நேர்மறையான முழு எண் N ஐ வழங்குகிறது, மேலும் சில முழு எண்கள் a, b, c. இங்கே நாம் ஒரு, பி மற்றும் சி நீளங்களில் எண்ணைப் பிரிக்க விரும்புகிறோம். பிரிவுகளின் எண்ணிக்கை அதிகபட்சமாக N ஐ நாம் பிரிக்க வேண்டும். எனவே சிக்கலை தீர்க்க, முதலில் ஒரு பேராசை அணுகுமுறையை முயற்சிப்போம். சிக்கலைத் தீர்க்க ஒரு பேராசை அணுகுமுறை a, b, மற்றும் c ஆகியவற்றில் மிகச் சிறியதைத் தேர்ந்தெடுப்பதாகும். இப்போது N ஐ குறைந்தபட்ச நீளத்துடன் பகுதிகளாகப் பிரிக்கிறோம். ஆனால் அதற்கு ஒரு பிடிப்பு உள்ளது, மிகச்சிறிய பிரிவு N ஐப் பிரிக்காவிட்டால் என்ன செய்வது? பின்னர் எங்களால் செய்ய முடியாத ஒரு மீதமுள்ள பகுதியுடன் எஞ்சியிருப்போம். எனவே, சில சந்தர்ப்பங்களில் பேராசை கொண்ட அணுகுமுறையைப் பயன்படுத்தி எங்களால் பதிலைக் கண்டுபிடிக்க முடியவில்லை என்பதை இது உறுதிப்படுத்துகிறது.

எனவே, பேராசை அணுகுமுறையைப் பயன்படுத்தி இதைச் செய்வதற்குப் பதிலாக. பயன்படுத்தி சிக்கலை தீர்க்கிறோம் மறுநிகழ்வு. N க்கு விடை தரும் ஒரு செயல்பாட்டை நாங்கள் செய்கிறோம், பின்னர் இந்த செயல்பாடு தன்னை Na, Nb மற்றும் Nc மதிப்புகளுடன் அழைக்கிறது. இவ்வாறு அசல் சிக்கல் சிறிய துணைப் பிரச்சினைகளாகப் பிரிக்கப்பட்டுள்ளது. இந்த சுழல்நிலை செயல்பாட்டின் அதிவேக நேர சிக்கலையும் நாம் குறைக்கலாம் டைனமிக் நிரலாக்க. டிபி உடனான நிரல் நேரியல் நேரத்தில் இயங்கும். ஏனென்றால், ஒரு சிறிய துணை சிக்கல்களுக்கான பதிலைச் சேமிக்கும் ஒரு டிபி வரிசையை உருவாக்குவோம். அவற்றின் முடிவு தேவைப்படும்போதெல்லாம் அவற்றை மீண்டும் மீண்டும் தீர்வு காண்பதற்குப் பதிலாக அவற்றைப் பயன்படுத்துகிறோம்.

குறியீடு

A, b மற்றும் c நீளங்களின் அதிகபட்ச எண்ணிக்கையைக் கண்டறிய சி ++ குறியீடு

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

int main()
{
  int n = 7, a = 5, b = 2, c = 3;
  int dp[n + 1];
  memset(dp, -1, sizeof(dp));
  // base case
  dp[0] = 0;
  for (int i = 0; i < n; i++)
  {
    if (dp[i] != -1) {
            if(i + a <= n )dp[i + a] = max(dp[i] + 1, dp[i + a]);
            if(i + b <= n )dp[i + b] = max(dp[i] + 1, dp[i + b]);
            if(i + c <= n )dp[i + c] = max(dp[i] + 1, dp[i + c]);
    }
  }
    cout<<dp[n];
}
3

A, b மற்றும் c நீளங்களின் அதிகபட்ச எண்ணிக்கையைக் கண்டறிய ஜாவா குறியீடு

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int n = 7, a = 5, b = 2, c = 3;
    int dp[] = new int[n+1];
    for(int i=0;i<=n;i++)dp[i] = -1;
    // base case
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
      if (dp[i] != -1) {
              if(i + a <= n )dp[i + a] = Math.max(dp[i] + 1, dp[i + a]);
              if(i + b <= n )dp[i + b] = Math.max(dp[i] + 1, dp[i + b]);
              if(i + c <= n )dp[i + c] = Math.max(dp[i] + 1, dp[i + c]);
      }
    }
    System.out.println(dp[n]);
  }
}
3

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), கொடுக்கப்பட்ட முழு எண் வரை நாம் ஒரு சுழற்சியை இயக்கியுள்ளோம். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (என்), மறு கணக்கீட்டைத் தவிர்ப்பதற்காக இடைநிலை முடிவுகளை சேமிப்பதற்காக 1 டி டிபி வரிசையை உருவாக்க வேண்டியிருந்தது. இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.