Biorąc pod uwagę tablicę, znajdź kombinacje n liczb, które są mniejsze niż c

Question

To jest trudne, przynajmniej dla moich minimalnych umiejętności c.

Zasadniczo użytkownik wprowadza listę cen do tablicy, a następnie żądaną liczbę przedmiotów, które chce kupić, a ostatecznie maksymalny koszt nie może przekroczyć.

Muszę sprawdzić, ile kombinacji żądanej liczby elementów jest mniejszych lub równych podanemu kosztowi.

Jeśli problem polegał na ustalonej liczbie elementów w kombinacji, powiedzmy 3, byłoby to o wiele łatwiejsze dzięki trzem pętlom wybierającym każdą cenę i dodawaniu ich do testu.

Miejsce, w którym się znajdujesz, to wymóg, aby użytkownik wprowadził dowolną liczbę elementów, aż do liczby elementów w tablicy.

To jest to, co postanowiłem na początku, zanim zdałem sobie sprawę, że użytkownik może określić kombinacje dowolnej liczby, a nie tylko trzy. Został stworzony przy pomocy podobnego tematu tutaj, ale znowu działa tylko wtedy, gdy użytkownik określi, że chce 3 elementy na kombinację. W przeciwnym razie nie działa.

// test if any combinations of items can be made 
    for (one = 0; one < (count-2); one++) // count -2 to account for the two other variables 
    { 
    for (two = one + 1; two < (count-1); two++) // count -1 to account for the last variable 
    { 
     for (three = two + 1; three < count; three++) 
     { 
     total = itemCosts[one] + itemCosts[two] + itemCosts[three]; 
     if (total <= funds) 
     { 
      // DEBUG printf("\nMatch found! %d + %d + %d, total: %d.", itemCosts[one], itemCosts[two], itemCosts[three], total); 
      combos++; 
     } 
     } 
    } 
    } 

O ile mogę powiedzieć, nie ma prostego sposobu na dostosowanie go do elastyczności w oparciu o pożądaną liczbę elementów na kombinację.

Byłbym wdzięczny za udzieloną pomoc.

Answer 1

Jedna z trików do spłaszczania iteracji zagnieżdżonych polega na użyciu rekursji.

Utwórz funkcję, która zajmuje całą tablicę elementów, które wybrałeś do tej pory, oraz liczbę przedmiotów, które wybrałeś do tego momentu. Algorytm powinien iść tak:

• Jeśli wybrali liczbę elementów równych swojej cel N, obliczyć sumę i sprawdzić go przed limitu
• Jeśli nie wybrali na tyle przedmiotów, dodać jedną więcej pozycji do listy i wykonaj wywołanie rekurencyjne.

Aby upewnić się, że nie wybierzesz tego samego elementu dwukrotnie, podaj najmniejszy indeks, z którego może wybrać dana funkcja. Deklaracja funkcji może wyglądać następująco:

int count_combinations(
    int itemCosts[] 
, size_t costCount 
, int pickedItems[] 
, size_t pickedCount 
, size_t pickedTargetCount 
, size_t minIndex 
, int funds 
) { 
    if (pickedCount == pickedTargetCount) { 
     // This is the base case. It has the code similar to 
     // the "if" statement from your code, but the number of items 
     // is not fixed. 
     int sum = 0; 
     for (size_t i = 0 ; i != pickedCount ; i++) { 
      sum += pickedItems[i]; 
     } 
     // The following line will return 0 or 1, 
     // depending on the result of the comparison. 
     return sum <= funds; 
    } else { 
     // This is the recursive case. It is similar to one of your "for" 
     // loops, but instead of setting "one", "two", or "three" 
     // it sets pickedItems[0], pickedItems[1], etc. 
     int res = 0; 
     for (size_t i = minIndex ; i != costCount ; i++) { 
      pickedItems[pickedCount] = itemCosts[i]; 
      res += count_combinations(
       itemCosts 
      , costCount 
      , pickedItems 
      , pickedCount+1 
      , pickedTargetCount 
      , i+1 
      , funds 
      ); 
     } 
     return res; 
    } 
} 

wywołać tę funkcję tak:

int itemCosts[C] = {...}; // The costs 
int pickedItems[N]; // No need to initialize this array 
int res = count_combinations(itemCosts, C, pickedItems, 0, N, 0, funds); 

Demo.

Answer 2

Można to zrobić za pomocą algorytmu backtracking. Jest to równoważne implementacji listy zagnieżdżonych for loop s. Można to lepiej zrozumieć, próbując zobaczyć schemat wykonywania sekwencji zagnieżdżonych dla pętli.

Na przykład powiedzmy, że zgodnie z prezentacją masz sekwencję 3 for s, a wykonanie kodu osiągnęło trzeci poziom (najgłębszy). Po przejściu wszystkich iteracji powracasz na drugi poziom for, gdzie przechodzisz do następnej iteracji, w której skoczysz ponownie na trzeci poziom for.Podobnie, gdy drugi poziom kończy całą swoją iterację, przeskakujesz z powrotem na pierwszy poziom for, który kontynuuje następną iterację, w której przeskakujesz na drugim poziomie, a stamtąd w trzecim.

Tak więc, na danym poziomie próbujesz przejść do głębszego (jeśli taki istnieje) i jeśli nie ma już kolejnych iteracji, powracasz do poziomu (z powrotem).

Stosując wycofywania można oznaczają zagnieżdżone for przez układ, w którym każdy z elementów jest zmienna Index: Tablica [0] jest wskaźnikiem dla for poziomu 0, i tak dalej.

Oto próbka realizacja dla swojego problemu:

#define NUMBER_OF_OBJECTS 10 
#define FORLOOP_DEPTH  4 // This is equivalent with the number of 
           // of nested fors and in the problem is 
           // the number of requested objects 
#define FORLOOP_ARRAY_INIT -1 // This is a init value for each "forloop" variable 
#define true 1 
#define false 0 
typedef int bool; 
int main(void) 
{ 
    int object_prices[NUMBER_OF_OBJECTS]; 
    int forLoopsArray[FORLOOP_DEPTH]; 
    bool isLoopVariableValueUsed[NUMBER_OF_OBJECTS]; 
    int forLoopLevel = 0; 

    for (int i = 0; i < FORLOOP_DEPTH; i++) 
    { 
     forLoopsArray[i] = FORLOOP_ARRAY_INIT; 
    } 
    for (int i = 0; i < NUMBER_OF_OBJECTS; i++) 
    { 
     isLoopVariableValueUsed[i] = false; 
    } 


    forLoopLevel = 0; // Start from level zero 
    while (forLoopLevel >= 0) 
    { 
     bool isOkVal = false; 

     if (forLoopsArray[forLoopLevel] != FORLOOP_ARRAY_INIT) 
     { 
      // We'll mark the loopvariable value from the last iterration unused 
      // since we'll use a new one (in this iterration) 
      isLoopVariableValueUsed[forLoopsArray[forLoopLevel]] = false; 
     } 

     /* All iterations (in all levels) start basically from zero 
     * Because of that here I check that the loop variable for this level 
     * is different than the previous ones or try the next value otherwise 
     */ 
     while ( isOkVal == false 
       && forLoopsArray[forLoopLevel] < (NUMBER_OF_OBJECTS - 1)) 
     { 
      forLoopsArray[forLoopLevel]++; // Try a new value 
      if (loopVariableValueUsed[forLoopsArray[forLoopLevel]] == false) 
      { 
       objectUsed[forLoopsArray[forLoopLevel]] = true; 
       isOkVal = true; 
      } 
     } 

     if (isOkVal == true) // Have we found in this level an different item? 
     { 
      if (forLoopLevel == FORLOOP_DEPTH - 1) // Is it the innermost? 
      { 
       /* Here is the innermost level where you can test 
       * if the sum of all selected items is smaller than 
       * the target 
       */ 
      } 
      else // Nope, go a level deeper 
      { 
       forLoopLevel++; 
      } 
     } 
     else // We've run out of values in this level, go back 
     { 
      forLoopsArray[forLoopLevel] = FORLOOP_ARRAY_INIT; 
      forLoopLevel--; 
     } 
    } 
}