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

Question

这是一个艰难的过程，至少对于我最起码的 c 技能来说是这样。

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

我需要检查所需数量的商品有多少组合小于或等于给定的成本。

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

让我感到难过的是要求用户输入任意数量的项目，最多为数组中的项目数。

这是我最初的决定，后来才意识到用户可以指定任意数字的组合，而不仅仅是三个。它是在此处类似主题的帮助下创建的，但同样只有在用户指定他想要每个组合 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++;
        }
      }
    }
  }

据我所知，没有简单的方法可以根据用户对每个组合所需的项目数量进行灵活调整。

如果能提供任何帮助，我将不胜感激。

Answer 1

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

创建一个函数，该函数接受您到目前为止选择的项目数组，以及您目前已拾取的项目数。该算法应该是这样的:

• 如果您选择的项目数量等于您的目标 N，请计算总和并根据限制检查它
• 如果您没有选择足够的项目，请在您的列表中再添加一项，然后进行递归调用。

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

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

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

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.