សំណុំអនុគូដែលធំជាងគេ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន google
ការសរសេរកម្មវិធីឌីណាមិក គណិតវិទ្យា

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ គូដែលអាចបែងចែកបានធំជាងគេបំផុត” បញ្ជាក់ថាអ្នកត្រូវបានគេផ្តល់នូវធាតុខុសគ្នាជាច្រើន។ រកប្រវែងធំបំផុតដែលគូនីមួយៗមានធាតុធំជាងដែលអាចបែងចែកបានដោយធាតុតូចៗ។

ឧទាហរណ៍

សំណុំអនុគូដែលធំជាងគេ

array = {1, 2, 4, 5, 8, 9, 16}
5

ការពន្យល់

សំណុំរងធំបំផុតគឺ ១, ២, ៤, ៨, ១៦ ដែលធ្វើតាមលក្ខខណ្ឌដែលបានបញ្ជាក់នៅក្នុងបញ្ហា។ ដោយសារប្រវែងនៃសំណុំរងនេះគឺ ៥ ចម្លើយគឺ ៥ ។

វិធីសាស្រ្ត

ចូរចាប់ផ្តើមជាមួយនឹងវិធីសាស្រ្តដែលឆោតល្ងង់។ រឿងសាមញ្ញបំផុតដែលអ្នកអាចគិតបានគឺបង្កើតសំណុំរងទាំងអស់ហើយបន្ទាប់មកពិនិត្យមើលថាតើសំណុំរងធ្វើតាមលក្ខខណ្ឌដែលបានផ្តល់ឱ្យ។ ប្រសិនបើវាធ្វើដូច្នេះទុកប្រវែងនៃសំណុំរង។ បន្តធ្វើបច្ចុប្បន្នភាពតម្លៃនេះជាមួយនឹងប្រវែងសំណុំរងធំជាងមុនប្រសិនបើអ្នករកឃើញថាណាមួយដែលពេញចិត្តនឹងលក្ខខណ្ឌដែលបានផ្តល់ឱ្យ។ ប៉ុន្តែវិធីសាស្រ្តនេះមិនមានប្រសិទ្ធភាពខ្ពស់ទេព្រោះវាទាមទារអោយបង្កើតជំនាន់រងទាំងអស់ដែលខ្លួនត្រូវការពេលវេលាស្វ័យគុណ។

ដូច្នេះដើម្បីដោះស្រាយបញ្ហាប្រកបដោយប្រសិទ្ធភាព។ យើងព្យាយាមបំបែកបញ្ហាទៅជាបញ្ហាតូចជាងមុន។ បញ្ហានិយាយថាគូទាំងអស់គួរតែបំពេញលក្ខខណ្ឌដែលលេខតូចជាងគួរតែបែងចែកលេខធំជាង។ ដូច្នេះប្រសិនបើយើងគិតអំពីវាយើងអាចគិតពីដំណោះស្រាយស្រដៀងនឹងបញ្ហា LIS ។ ការកើនឡើងយូរបំផុត បញ្ហានិយាយថាត្រូវរកប្រវែងនៃសំណុំរងធំបំផុតដែលកំពុងកើនឡើងជាលំដាប់។ យើងអាចធ្វើអ្វីដែលស្រដៀងគ្នាដោយប្រើ ការសរសេរកម្មវិធីឌីណាមិក។ ដំបូងយើងនឹងតំរៀបជួរ។ បន្ទាប់មកសម្រាប់ធាតុនីមួយៗយើងនឹងឃើញធាតុទាំងអស់មុនពេលវាហើយពិនិត្យមើលថាតើធាតុណាមួយបែងចែកធាតុបច្ចុប្បន្ននេះ។ ប្រសិនបើធាតុណាមួយបែងចែកធាតុបច្ចុប្បន្នយើងដឹងថាយើងអាចបន្ថែមធាតុបច្ចុប្បន្នទៅសំណុំរងនោះ។

ដូច្នេះយើងបង្កើតអាដាប់ធ័រ DP ដែលធាតុអ៊ីសបង្ហាញប្រវែងនៃសំណុំរងធំបំផុតដែលមានធាតុបច្ចុប្បន្នជាធាតុធំបំផុតរបស់វា។ ហើយសំណុំរងបំពេញនូវលក្ខខណ្ឌដែលបានដាក់លើបញ្ហា។

លេខកូដ

លេខកូដ C ++ សម្រាប់សំណុំរងគូចែកធំជាងគេ

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

int largestDivisibleSubset(vector<int>& nums) {
    int n = nums.size();
    if(n==0)return 0;
    sort(nums.begin(), nums.end());
    int dp[n], ans = INT_MIN;
    for(int i=0;i<n;i++){
        dp[i] = 1;
        for(int j=i-1;j>=0;j--)
            if(nums[i]%nums[j] == 0){
                if((dp[j]+1)>dp[i]){
                    dp[i] = dp[j]+1;
                    ans = max(ans, dp[i]);
                }
            }
    }
    return ans;
}

int main(){
  int n;cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin>>v[i];
  int len = largestDivisibleSubset(v);
  cout<<len<<endl;
}
7
1 2 4 5 8 9 16
5

លេខកូដចាវ៉ាសម្រាប់សំណុំរងគូដែលអាចបែងចែកធំជាងគេ

import java.util.*;
class Main{
  
  static int largestDivisibleSubset(ArrayList<Integer> nums) {
      int n = nums.size();
      if(n==0)return 0;
      Collections.sort(nums);
      int dp[] = new int[n];
      int ans = Integer.MIN_VALUE;
      for(int i=0;i<n;i++){
          dp[i] = 1;
          for(int j=i-1;j>=0;j--)
              if(nums.get(i)%nums.get(j) == 0){
                  if((dp[j]+1)>dp[i]){
                      dp[i] = dp[j]+1;
                      ans = Math.max(ans, dp[i]);
                  }
              }
      }
      return ans;
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> v = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      v.add(a);
    }
    int len = largestDivisibleSubset(v);
    System.out.println(len);
  	}
}
7
1 2 4 5 8 9 16
5

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N ^ ២), ដោយសារតែនៅក្នុងបញ្ហាយើងឆ្លងកាត់រាល់ធាតុទាំងអស់ដែលមានមុនធាតុបច្ចុប្បន្ន។ ពេលវេលាស្មុគស្មាញគឺពហុធា។

ភាពស្មុគស្មាញនៃលំហ

O (N), ចាប់តាំងពីយើងបានប្រើអារេសម្រាប់រក្សាទុកតម្លៃជាតារាង DP ។ ភាពស្មុគស្មាញនៃលំហគឺលីនេអ៊ែរ។