Với một mảng, hãy tìm các kết hợp của các số n nhỏ hơn c

Question

Đây là một kết quả khó, ít nhất là cho các kỹ năng tối thiểu của tôi.

Về cơ bản, người dùng nhập danh sách giá vào một mảng và sau đó số lượng mục mong muốn mà anh muốn mua và cuối cùng là chi phí tối đa không vượt quá.

Tôi cần kiểm tra số lượng kết hợp của số lượng mục mong muốn nhỏ hơn hoặc bằng chi phí đã cho.

Nếu vấn đề là số mục cố định trong kết hợp, giả sử 3, nó sẽ dễ dàng hơn nhiều với chỉ ba vòng chọn mỗi giá và thêm chúng để kiểm tra.

Nơi tôi nhận được bối cảnh là yêu cầu người dùng nhập bất kỳ số lượng mục nào, tối đa số mục trong mảng.

Đây là những gì tôi quyết định lúc đầu, trước khi nhận ra rằng người dùng có thể chỉ định các kết hợp của bất kỳ số nào, không chỉ ba. Nó được tạo ra với sự giúp đỡ từ một chủ đề tương tự ở đây, nhưng một lần nữa nó chỉ hoạt động nếu người dùng chỉ định anh ta muốn 3 mục cho mỗi kết hợp. Nếu không nó không hoạt động.

// 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++; 
     } 
     } 
    } 
    } 

Theo tôi có thể dễ dàng điều chỉnh tính linh hoạt dựa trên số mục mong muốn của người dùng trên mỗi kết hợp.

Tôi thực sự đánh giá cao bất kỳ trợ giúp nào được cung cấp.

Answer 1

Một mẹo để làm phẳng các lần lặp lồng nhau là sử dụng đệ quy.

Thực hiện một chức năng nhận một loạt các mục bạn đã chọn cho đến thời điểm này và số lượng mục bạn đã chọn cho đến thời điểm này. Thuật toán nên đi như thế này:

• Nếu bạn đã chọn số lượng các mục bằng với mục tiêu của bạn của N, tính tổng và kiểm tra xem nó chống lại giới hạn
• Nếu bạn chưa chọn đủ các mặt hàng, thêm một thêm mục vào danh sách của bạn và thực hiện cuộc gọi đệ quy.

Để đảm bảo bạn không chọn cùng một mục hai lần, hãy chuyển chỉ mục nhỏ nhất mà chức năng có thể chọn. Việc kê khai của hàm có thể trông như thế này:

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; 
    } 
} 

Bạn gọi hàm này như sau:

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

Điều này có thể được thực hiện bằng cách sử dụng một thuật toán backtracking. Điều này tương đương với việc triển khai danh sách số lồng nhau for loop s. Điều này có thể được hiểu rõ hơn bằng cách cố gắng xem mẫu thực hiện của một chuỗi lồng nhau cho các vòng lặp. Ví dụ:

Ví dụ: giả sử bạn có, như bạn đã trình bày, một chuỗi gồm 3 for và việc thực thi mã đã đạt đến cấp độ thứ ba (trong cùng). Sau khi điều này đi qua tất cả các lần lặp của nó, bạn quay trở lại mức thứ hai for nơi bạn đi đến bước lặp tiếp theo mà trong đó bạn nhảy lại ở cấp độ thứ ba for.Tương tự như vậy, khi cấp độ thứ hai kết thúc tất cả các lần lặp của nó, bạn nhảy trở lại mức đầu tiên for tiếp tục với lần lặp tiếp theo mà bạn nhảy ở cấp độ thứ hai và từ đó trong lần thứ ba. Vì vậy, ở một mức độ nhất định, bạn hãy thử đi sâu hơn (nếu có) và nếu không có nhiều lần lặp lại, bạn quay trở lại một mức độ (theo dõi ngược lại).

Sử dụng backtracking bạn đại diện cho lồng nhau for bởi một mảng trong đó mỗi phần tử là biến chỉ mục: mảng [0] là chỉ mục cho for cấp 0, v.v.

Đây là một thực hiện mẫu cho vấn đề của bạn:

#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--; 
     } 
    } 
}