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

概述这是一个艰难的,至少我的最低技能. 基本上,用户将价格列表输入到阵列中,然后输入他想要购买的所需数量的项目,最后是不超过的最大成本. 我需要检查所需数量的项目的组合数量是否小于或等于给定的成本. 如果问题是组合中固定数量的项目,比如说3,只需要三个循环选择每个价格并添加它们进行测试就会容易得多. 我感到难过的地方是要求用户输入任意数量的项目,直到数组中的项目数量. 这是我最初决定的,然后才意识到用 这是一个艰难的,至少我的最低技能.

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

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

如果问题是组合中固定数量的项目,比如说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++;        }      }    }  }

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

我真的很感激任何帮助.

解决方法 扁平嵌套迭代的一个技巧是使用递归.

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

>如果您已选择等于目标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 costsint pickedItems[N]; // No need to initialize this arrayint res = count_combinations(itemCosts,C,N,funds);

Demo.

总结

以上是内存溢出为你收集整理的给定一个数组,找到小于c的n个数字的组合全部内容，希望文章能够帮你解决给定一个数组,找到小于c的n个数字的组合所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。