A, b এবং c এর দৈর্ঘ্যের খন্ডের সর্বাধিক সংখ্যা  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক কালো শিলা ByteDance Citrix গুগল তেরদাটা উবার
ডায়নামিক প্রোগ্রামিং

সমস্যাটি "a, b এবং c এর দৈর্ঘ্যের সর্বাধিক সংখ্যার অংশ" বলে দেয় যে আপনাকে একটি ধনাত্মক পূর্ণসংখ্যার এন দেওয়া হয়েছে এবং আপনাকে N এর সাহায্যে গঠন করা যায় এমন a, b, এবং c এর দৈর্ঘ্যের সর্বাধিক সংখ্যার সন্ধান করতে হবে need

উদাহরণ  

A, b এবং c এর দৈর্ঘ্যের খন্ডের সর্বাধিক সংখ্যাপিন

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

ব্যাখ্যা

এখানে যদি আমরা লোভী পদ্ধতির সাথে চলে যাই তবে ক্ষুদ্রতম বিভাগ (= 2) দিয়ে সমস্ত বিভাগকে কাটতে চেষ্টা করি। আমরা আকারের শেষ বিভাগটি তৈরি করতে সক্ষম হব না Thus এভাবে আমরা দৈর্ঘ্য 1 কে দুটি 4 দৈর্ঘ্যের বিভাগ এবং একটি 2 দৈর্ঘ্যের বিভাগের সাথে ভাগ করব divide

অভিগমন  

সমস্যাটি আমাদের একটি ধনাত্মক পূর্ণসংখ্যার এন সরবরাহ করে এবং কিছু অন্যান্য পূর্ণসংখ্যার ক, খ, সি। এখানে আমরা সংখ্যাটি a, b এবং c এর দৈর্ঘ্যে ভাগ করতে চাই। আমাদের 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

জটিলতা বিশ্লেষণ  

সময় জটিলতা

চালু), কারণ প্রদত্ত পূর্ণসংখ্যা পর্যন্ত আমরা কেবল একটি লুপ চালাই ran সুতরাং সময় জটিলতা রৈখিক হয়।

আরো দেখুন
মি দ্বারা বিভাজ্য অঙ্ক সহ সাবসেট

স্পেস জটিলতা ity

চালু), কারণ পুনর্বিবেচনা এড়াতে মধ্যবর্তী ফলাফলগুলি সংরক্ষণ করার জন্য আমাদের একটি 1D ডিপি অ্যারে তৈরি করতে হয়েছিল। সুতরাং স্থান জটিলতাও লিনিয়ার।