Algorytm wywoływania jak najmniejszej liczby połączeń z API

Question

W moim programie będę miał wiele tablic z około 40 000 ciągów o różnej długości (od 10 do 5000 znaków), muszę wysłać tę tablicę do API, które akceptuje tylko 5 000 znaków naraz.

Aby wykonać jak najmniejszą liczbę połączeń API, potrzebuję znaleźć najlepsze kombinacje ciągów do wysłania za każdym razem.

Na przykład, jeśli mam tablicę o innej długości {3, 5, 10, 3, 4, 1, 4}, a maksymalna długość api to 10. Powinno to zwrócić {10}, {4 1 5 }, {3 3 4}.

Przeglądałem różne algorytmy, ale nikt nie zaspokaja mojej potrzeby. (Suma podzbioru i inne)

Każda pomoc jest bardzo doceniana!

Answer 1

Twój problem to Bin Packing problem.Proszę znaleźć całkiem ładne rozwiązanie w następującym artykule: A new algorithm for optimal bin packing Richarda Korf (patrz przykład problemu tam)

Spójrzmy na przykład na tablicy:

MAXSIZE=20 
[1 2 4 5 7 10 11] 

algorytmem od wskazanej papieru dostaniesz:

[11 4 5] [10 7 2 1] 

W skrócie algorytm ten build bin przez:

1. wkładka do bin maksymalnego elementu

2. Szukaj wszystkich elementów, które pasuje do objętości lewej i maksymalizacji ich suma

Na przykład w naszym przypadku pierwszym krokiem byłoby:

# Take max element 
[11] 
# We have 9 volume left 
# All smaller are [1 2 4 5 7] - greedy would take 7 in this case 
# 4 and 5 sums up to 9 which is best fit in this case so first bin become: 
[11 5 4] 
# Next step: take max 
[10] 
# we have 10 volume left. elements lower than 10: 
# [1 2 7] 
# this sums up to 10 in this case giving second bin 
[10 7 2 1] 

I właśnie przykład chciwego lub wymienionego:

ARR = [3, 3, 5, 5, 5, 5, 14] 
BINSIZE = 20 
Greedy result: 
Size 3: 
[[14, 5], [5, 5, 5, 3], [3]] 
Mentioned alg result (size 2): 
[[14, 3, 3], [5, 5, 5, 5]] 

Als o możesz być zainteresowany sekcją "Dokładny algorytm" na stronie wiki.

Answer 2

Zdecydowanie wygląda na problem z programowaniem dynamicznym. Twoje pytanie jest podobne do Subset Sum problem, z tą różnicą, że zamiast sprawdzać, czy taki podzbiór istnieje, chcesz zwrócić wszystkie takie podzestawy.

Link ten wydaje się być blisko tego, co trzeba: http://www.careercup.com/question?id=12899672

Programowanie dynamiczne jest często dość trudne do owinąć wokół twojej głowie. Mam nadzieję, że ktoś inny udzieli dokładnego wyjaśnienia (także dla mnie), ale mam nadzieję, że to da ci od czego zacząć.

Answer 3

To jest problem programowania dynamicznego (problem z sumą podzestawu) z odmianą. Nie tylko chcemy sprawdzić, czy suma istnieje, ale chcemy również znaleźć wszystkie różne podzbiory.

Tworzymy 2-d logiczną tablicę wyników sum (wiersze) - kontra - liczbę (col), co jest typowe w wielu problemach z DP. Aby znaleźć podzbiory, które dokładnie pasują do sumy, możemy wywołać funkcję backtracking w tabeli odnośników, aby znaleźć możliwe prawidłowe sumy.

bool backtrack(bool **subset, int sum, int a[], int n) { 
    if(sum == 0) { // Sum possible 
     return true; 
    } 
    if(sum < 0) { //Sum not possible 
     return false; 
    } 

    for(int j=1; j<=n; j++) { 
     if(subset[sum][j] == true) { 
      int val = a[j-1]; 

      // If val is included, can we have a valid sum? 
      bool valid = backtrack(subset, sum-val, a, j-1); 
      if(valid == true) { 
       printf("%d ", val); 
       return true; 
      } 
     } 
    } 
    return false; 
} 

Możemy zadzwonić powyższa funkcja w ten sposób, aby wydrukować kombinacji liczb, jednej kombinacji w każdym row-

for(j=1; j<=n; j++) { 
    if(subset[sum][j] == 1) { //For every col which is =1 for the sum'th row 
     bool valid = backtrack(subset, sum-a[j-1], a, j-1); 
     if(valid) { 
      printf("%d\n", a[j-1]); 
     } 
    } 
} 

Answer 4

Jak to działa dla Ciebie? Oczywiście, możesz zmienić maksimum, aby być kimkolwiek chcesz, i prawdopodobnie zmienić to ustawienie na funkcję wywołującą, ale pozostawię te wybory do ciebie.

To zadziałało dla mnie, daj mi znać, jeśli masz jakiekolwiek problemy z tym.

List<List<string>> Chunk(List<string> inputStrings) 
{ 
    List<List<string>> retVal = new List<List<string>>(); 

    List<string> sortedStrings = inputStrings.OrderByDescending(s => s.Length).ToList(); 

    while (sortedStrings.Any()) 
    { 
     List<string> set = new List<string>(); 
     int max = 10; 

     for (int i = 0; i < sortedStrings.Count(); ++i) 
     { 
      if (max == 0) 
       break; 
      if (max - sortedStrings[i].Length < 0) 
       continue; 

      set.Add(sortedStrings[i]); 
      max -= sortedStrings[i].Length; 
      sortedStrings.RemoveAt(i); 
      --i; 
     } 

     if(set.Any()) 
      retVal.Add(set); 
    } 

    return retVal; 
} 

Uwaga: To jest C#. W razie potrzeby mogę je ponownie napisać w innym języku lub z innymi strukturami danych.

Answer 5

To wydaje się być rozwiązane przez algorytm Greedy'ego, a nie algorytm wstecznego działania, który powinien zostać wykonany przed wysłaniem ciągu znaków do interfejsu API.