လှံတံဖြတ်တောက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ နေခြည် Flipkart Google JP Morgan Microsoft က
Dynamic Programming

ပြProbleနာဖော်ပြချက်

“ ဖြတ်တောက်ခြင်း” ပြနာကသင့်အားအချို့သောရှည်လျားသောလှံတံတစ်ချောင်းပေးပြီးထည့်သွင်းထားသည့်အရှည်ထက်ငယ်သောသို့မဟုတ်ညီမျှသောချည်မျှင်အားလုံး၏စျေးနှုန်းများကိုသင့်အားပေးသည်ဟုဖော်ပြသည်။ ဆိုလိုသည်မှာကျွန်ုပ်တို့သည်လှံတံ၏အရှည်သည် was ဖြစ်ခြင်းကြောင့် ၁ မှ n အထိအရှည်၏တန်ဖိုးကိုကျွန်ုပ်တို့သိကြပါသည်။ ဤနေရာတွင်သတိပြုရမည့်အရာတစ်ခုမှာမတူညီသောအရှည်၏လှံတံအတွက်စျေးနှုန်းကိုညီမျှစွာမဖြန့်ဝေခြင်းဖြစ်သည်။ အချို့သောအရှည်ရှိသည့်ချောင်းများသည်အခြားသူများထက်ပိုမိုစျေးကြီးသည်။ ဤချောင်းများသည်အခြားအရှည်အမျိုးမျိုးရှိသောချောင်းများနှင့်နှိုင်းယှဉ်ပါကပိုမိုရှည်လျားနိုင်သည်သို့မဟုတ်ရှိနိုင်သည်။

နမူနာ

length = 1 2 3 4 5 6 7
price = 4 5 6 7 7 1 1
28

 

လှံတံဖြတ်တောက်ရှင်းလင်းချက်။ ။ ကျွန်ုပ်တို့အကောင်းဆုံးလုပ်နိုင်သည်မှာအရှည် ၇ ချောင်းဖြစ်ပြီးကုန်ကျစရိတ်၏ ၂၈ အကောင်းဆုံးရလဒ်ကိုပေးနိုင်သည်။

ချဉ်းကပ်နည်း

ဒီတော့ဒီပြproblemနာကိုဖြေရှင်းဖို့အတွက်သင်ကဒီပြrecနာကိုပြန်လည်ထူထောင်ဖို့စဉ်းစားနိုင်သည်။ ထိုချဉ်းကပ်နည်းမျှမျှတတမှန်သည်။ ဒီတော့ဒီပြrecနာကိုဘယ်လိုဖြေရှင်းမလဲဆိုတာဆွေးနွေးကြည့်ရအောင်။ ကျနော်တို့အမျိုးမျိုးသောအရှည်အပိုင်းအစများအတွက်လှံတံကိုဖြတ်ဖို့ကြိုးစားနိုင်ပါတယ်။ ထို့နောက်ကျွန်ုပ်တို့သည်ချောင်းများအားလုံးဖြတ်တောက်ပြီးနောက်ဖွဲ့စည်းထားသောချောင်းများ၏စျေးနှုန်းကိုတွက်ချက်သည်။ ဒါပေမယ့်ငါတို့ပြောနေတာကငါတို့ချောင်းတွေဖြတ်ဖို့နည်းလမ်းတွေရှာဖို့လိုတယ် ဤစစ်ဆင်ရေးသည်အလွန်အကုန်အကျများပြီးအချိန်ရှုပ်ထွေးမှုလည်းရှိသည်။ ဒီတော့ဒီတွက်ချက်မှုတွေကိုတစ်နည်းနည်းနဲ့လျှော့ဖို့လိုတယ်။ ကျွန်ုပ်တို့သည်ဖြတ်တောက်သည့်အချိန်တွင်လှံတံ၏အစိတ်အပိုင်းတစ်ခု၏ကုန်ကျစရိတ်ကိုထည့်သွင်းပါကအကောင်းဆုံးဖြစ်နိုင်သည်။ ထိုအခါသေးငယ်တဲ့ကြိမ်လုံးနှင့်အတူပြtheနာကိုထပ်ဖြေရှင်းပါ။ သို့သော်ဤသည်မလုံလောက်ပါ၊ ဤ algorithm သည်အဆသုံးရန်အချိန်ယူနေဆဲဖြစ်သည်။

လှံတံပြproblemနာကိုဖြတ်တောက်မှုများအတွက် recursive ပုံသေနည်းဖြစ်ပါတယ်

cuttingRod(n) = max(cost[i] + cuttingRod(n-i-1)) where i is in range from 0 to n-1

ထို့ကြောင့်ကျွန်ုပ်တို့သည် algorithm မည်သို့အလုပ်လုပ်သည်ကိုခေတ္တမျှကြည့်လျှင်။ ကျနော်တို့ဖြတ်တောက်ခြင်းကိုဖြတ်တောက်ခြင်းကိုဆက်လက်လုပ်ဆောင်နေသော cutRod (n-1)၊ motongRod (n-2)၊ CutRod (i) ကိုအကြိမ်များစွာခေါ်သည်။ ဒီတန်ဖိုးတွေကိုသိမ်းဆည်းမယ်ဆိုရင်ပိုကောင်းတယ်။ ဒါဆိုငါတို့သုံးမယ် Dynamic Programming ဤအမလိုအပ်သောကွန်ပျူတာများကိုလျှော့ချရန်။

ကုဒ်

လှံတံကိုဖြတ်တောက်ဘို့ C ++ ကုဒ်

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

int cuttingRod(vector<int> &cost) 
{
  int n = cost.size();
  int dp[n+1]; dp[0] = 0;

  for(int i=1;i<=n;i++){
    dp[i] = INT_MIN;
    for(int j=0;j<i;j++)
      dp[i] = max(dp[i], cost[j]+dp[i-j-1]);
  }
  return dp[n];
} 

int main(){
  // length of input rod
  int n;cin>>n;
  // store prices for length 1 to n
  vector<int> cost(n);
  for(int i=0;i<n;i++)
    cin>>cost[i];
  int maxCost = cuttingRod(cost);
  cout<<maxCost;
}
7
4 5 6 7 7 1 1
28

လှံတံကိုဖြတ်တောက်ဘို့ဂျာဗားကုဒ်

import java.util.*;
class Main{
  
  static int cuttingRod(ArrayList<Integer> cost){
    int n = cost.size();
    int dp[] = new int[n+1];
    dp[0] = 0;

    for(int i=1;i<=n;i++){
      dp[i] = Integer.MIN_VALUE;
      for(int j=0;j<i;j++)
        dp[i] = Math.max(dp[i], cost.get(j)+dp[i-j-1]);
    }
    return dp[n];
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // length of input rod
    int n = sc.nextInt();
    // store prices for length 1 to n
    ArrayList<Integer> cost = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      cost.add(a);
    }
    int maxCost = cuttingRod(cost);
    System.out.println(maxCost);
  }
}
7
4 5 6 7 7 1 1
28

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N ^ 2)ဘာဖြစ်လို့လဲဆိုတော့ကျနော်တို့ကအောက်ခြေ -DP ချဉ်းကပ်နည်းကိုသုံးပြီးသေးငယ်တဲ့အရှည်ချောင်းတွေရဲ့ကုန်ကျစရိတ်ကိုမွမ်းမံနေတယ်။ ဤသည်ကထပ်ညွှန်းကိန်းတွင် polynomial အချိန်အထိဖြေရှင်းသောပြtheနာကိုလျှော့ချစေသည်။

အာကာသရှုပ်ထွေးမှု

အို (N)ဘာဖြစ်လို့လဲဆိုတော့ဒီအာကာသကို DP ဇယားမှာရှိတဲ့တန်ဖိုးတွေကိုသိမ်းဆည်းဖို့သုံးတာပဲ။