A, b և c երկարությունների հատվածների առավելագույն քանակը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Blackrock ByteDance Citrix Google Տերադատա Uber
Դինամիկ ծրագրավորում

«A, b և c երկարությունների հատվածների առավելագույն քանակը» խնդրում նշվում է, որ ձեզ տրվում է N ամբողջ դրական թիվ, և դուք պետք է գտնեք a, b և c երկարությունների հատվածների առավելագույն քանակը, որոնք կարող են կազմվել N- ի միջոցով:

Օրինակ

A, b և c երկարությունների հատվածների առավելագույն քանակը

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

բացատրություն

Եթե ​​մենք գնում ենք ագահ մոտեցմամբ, փորձելով կտրել ամենափոքր հատվածով բոլոր հատվածները (= 2): Մենք չենք կարողանա ստեղծել 1-ին չափի վերջին հատվածը: Այսպիսով, 4 երկարությունը բաժանում ենք երկու 2 երկարության և մեկ 4 երկարությունների հատվածների:

Մոտեցում

Խնդիրը մեզ տալիս է դրական ամբողջ թիվ N, և մի շարք այլ ամբողջ թվեր a, b, c: Այստեղ ուզում ենք թիվը բաժանել a, b և c երկարությունների վրա: Մենք պետք է N բաժանենք այնպես, որ հատվածների քանակը առավելագույն լինի: Այսպիսով, խնդիրը լուծելու համար եկեք նախ փորձենք ագահ մոտեցում ցուցաբերել: Խնդիրը լուծելու ագահ մոտեցում է a, b և c փոքրերից ընտրելը: Այժմ մենք բաժանում ենք N- ի նվազագույն երկարությամբ հատվածների: Բայց դրան մի կարևորություն կա, ի՞նչ կլինի, եթե ամենափոքր հատվածը չի բաժանում N- ն: Այդ դեպքում մեզ կմնա մնացորդային հատված, որը հնարավոր չէ կատարել: Այսպիսով, սա հաստատում է, որ որոշ դեպքերում մենք չենք կարող գտնել պատասխանը `օգտագործելով ագահ մոտեցում:

Այնպես որ, փոխարենը դա անելու համար օգտագործեք ագահ մոտեցում: Մենք խնդիրը լուծում ենք ՝ օգտագործելով հետադարձություն, Մենք կատարում ենք մի ֆունկցիա, որը մեզ տալիս է N- ի պատասխանը, ապա այս ֆունկցիան իրեն անվանում է Na, Nb և Nc արժեքներով: Այսպիսով, սկզբնական խնդիրը բաժանվել է ավելի փոքր ենթախնդիրների: Մենք նաև կարող ենք նվազեցնել այս ռեկուրսիվ ֆունկցիայի ցուցիչ ժամանակի բարդությունը ՝ օգտագործելով դինամիկ ծրագրավորում, Pրագիրը DP- ով կգործարկի գծային ժամանակում: Քանի որ մենք կստեղծենք DP զանգված, որը կպահպանի պատասխանը փոքր ենթածրագրերի համար: Եվ երբ որ դրանց արդյունքն է պահանջվում, մենք պարզապես օգտագործում ենք դրանք փոխարենը փոխհատուցելու, ինչպես արեցինք ռեկուրսիվ լուծման մեջ:

Կոդ

C ++ ծածկագիր `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

Java կոդ ՝ 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք ուղղակի մի օղակ ենք գործարկել մինչև տրված ամբողջ ամբողջ թիվը: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք պետք է ստեղծեինք 1D DP զանգված միջանկյալ արդյունքները պահելու համար ՝ վերահաշվարկից խուսափելու համար: Այսպիսով, տարածության բարդությունը նույնպես գծային է: