给定一个数组，找到小于c的n个数字的组合

This is a tough one, at least for my minimal c skills.

这是一个艰难的，至少我的最低技能。

Basically, the user enters a list of prices into an array, and then the desired number of items he wants to purchase, and finally a maximum cost not to exceed.

基本上，用户将价格列表输入到阵列中，然后输入他想要购买的所需数量的项目，最后是不超过的最大成本。

I need to check how many combinations of the desired number of items are less than or equal to the cost given.

我需要检查所需数量的项目的组合数量是否小于或等于给定的成本。

If the problem was a fixed number of items in the combination, say 3, it would be much easier with just three loops selecting each price and adding them to test.

如果问题是组合中固定数量的项目，比如说3，只需要三个循环选择每个价格并添加它们进行测试就会容易得多。

Where I get stumped is the requirement that the user enter any number of items, up to the number of items in the array.

我感到难过的地方是要求用户输入任意数量的项目，直到数组中的项目数量。

This is what I decided on at first, before realizing that the user could specify combinations of any number, not just three. It was created with help from a similar topic on here, but again it only works if the user specifies he wants 3 items per combination. Otherwise it doesn't work.

这是我最初决定的，然后才意识到用户可以指定任意数字的组合，而不仅仅是三个。它是在这里的类似主题的帮助下创建的，但同样只有当用户指定他想要每个组合3个项目时它才有效。否则它不起作用。

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

As far as I can tell there's no easy way to adapt this to be flexible based on the user's desired number of items per combination.

据我所知，根据用户所需的每个组合的项目数量，没有简单的方法可以使其灵活适应。

I would really appreciate any help given.

我真的很感激任何帮助。

2 个解决方案

#1

One trick to flattening nested iterations is to use recursion.

扁平嵌套迭代的一个技巧是使用递归。

Make a function that takes an array of items that you have selected so far, and the number of items you've picked up to this point. The algorithm should go like this:

创建一个函数，该函数包含您到目前为止所选择的项目数，以及您在此时选择的项目数。算法应该是这样的：

• If you have picked the number of items equal to your target of N, compute the sum and check it against the limit
• 如果您已选择等于目标N的项目数，请计算总和并根据限制进行检查
• If you have not picked enough items, add one more item to your list, and make a recursive call.
• 如果您没有选择足够的项目，请在列表中再添加一项，然后进行递归调用。

To ensure that you do not pick the same item twice, pass the smallest index from which the function may pick. The declaration of the function may look like this:

为确保您不会选择相同的项目两次，请传递函数可以选择的最小索引。函数的声明可能如下所示：

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

You call this function like this:

你可以这样调用这个函数：

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.

演示。

#2

This can be done by using a backtracking algorithm. This is equivalent to implementing a list of nested for loops. This can be better understood by trying to see the execution pattern of a sequence of nested for loops.

这可以通过使用回溯算法来完成。这相当于实现嵌套for循环列表。通过尝试查看嵌套for循环序列的执行模式可以更好地理解这一点。

For example lets say you have, as you presented, a sequence of 3 fors and the code execution has reached the third level (the innermost). After this goes through all its iterations you return to the second level for where you go to the next iteration in which you jump again in third level for. Similarly, when the second level finishes all its iteration you jump back to the first level for which continues with the next iteration in which you jump in the second level and from there in the third.

例如，假设您已经提供了一系列3个fors，并且代码执行已达到第三级（最里面）。在经历了所有迭代后，您将返回第二级，进入下一次迭代，再次跳转到第三级。类似地，当第二级完成它的所有迭代时，你跳回到第一级，继续下一次迭代，你跳到第二级，然后从第三级跳到第三级。

So, in a given level you try go to the deeper one (if there is one) and if there are no more iterations you go back a level (back track).

因此，在给定的级别中，您尝试转到更深的一个（如果有的话），如果没有更多的迭代，则返回一个级别（后退轨道）。

Using the backtracking you represent the nested for by an array where each element is an index variable: array[0] is the index for for level 0, and so on.

使用回溯表示由数组嵌套，其中每个元素都是索引变量：array [0]是级别0的索引，依此类推。

Here is a sample implementation for your problem:

以下是您的问题的示例实现：

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