算法来确定物品的可能的组 [英] Algorithm to determine possible groups of items

问题描述

我抓我的头试图做到这一点，它吃了我。我知道这是不是那么复杂。我有多个项目，这个数目可以是等于或大于3。然后，我需要确定组将完成全部项目的可能的组合。唯一的限制是，该基团应具有三个或更多的项目，不超过（但包括）七品。

I am scratching my head trying to do this and it's eating me up. I know it is not THAT complex. I have a number of items, this number can be equal or greater than three. Then I need to determine the possible combination of group of items that will complete the total. The only restriction it's that the groups should have three or more items, not exceeding (but including) seven items.

例如：

如果我有7个项目，那么我可以有这些可能的组：

If I have 7 items, then I could have these possible groups:

• 1组的7个项目。
• 1组4个项目和1组3项。

如果我有12个项目，我可以有这些可能的组：

If I have 12 items, I could have these possible groups:

• 4组，每组3项。
• 3组，每组4项。
• 2组，每组6项。
• 1组7件+ 1小组的5个项目。
• 2组，每组3和1组6项。
• 1组3，1组4个和1组5个项目。
• ...

我想到了递归和开始实施的算法。这显然​​不工作。我吸的递归。很多。

I thought about recursion and started implementing the algorithm. It's obviously not working. I suck at recursion. A lot.

//Instance Fields
public List<ArrayList<String>> options;

//Method that will generate the options. The different options are 
//stored in a list of "option". An individual option will store a list of
//strings with the individual groups.
public void generateOptions(int items, ArrayList<String> currentOption){

    //If the current option is null, then create a new option.
    if(currentOption == null){
        currentOption = new ArrayList<String>();
    }
    if(items < 3){
        //If the number of items is less than three then it doesn't comply with the 
        //requirements (teams should be more or equal than three. 
        currentOption.add("1 group of "+items+" items");
        options.add(currentOption);
    }
    else{
        //I can make groups of 3,4,5,6 and 7 items.
        for(int i = 3;i<=7;i++){
            if(items%i == 0){ 
                // If the number of items is divisible per the current number, 
                // then a possible option could be items/i groups of i items. 
                // Example: Items = 9. A possible option is 3 groups of 3 items.
                currentOption.add(items/i +" groups of "+ i+" items");
                options.add(currentOption);
            }
            else{
                // If the number of items - the current number is equal or greater than
                // three, then a possible option could be a group of i items
                // and then I'll have items-i items to separate in other groups.
                if(items - i >=3){
                    currentOption.add("1 group of "+i+" items");
                    generateOptions(items-i,currentOption);
                }
            }
        }
    }
}

感谢您的帮助！

Thanks for your help!!!

推荐答案

下面是一个算法（如pressed在C ++中）来解决这个问题的一个更普遍的版本， 与上加数任意上限和下限，可能出现在每个分区中：

Here's an algorithm (expressed in C++) to solve a more general version of the problem, with arbitrary upper and lower bounds on the addends that may appear in each partition:

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> Partition;
typedef vector<Partition> Partition_list;

// Count and return all partitions of an integer N using only 
// addends between min and max inclusive.

int p(int min, int max, int n, Partition_list &v)
{
   if (min > max) return 0;
   if (min > n) return 0;     
   if (min == n) {
      Partition vtemp(1,min);
      v.push_back(vtemp);
      return 1;
   }
   else {
     Partition_list part1,part2;
     int p1 = p(min+1,max,n,part1);
     int p2 = p(min,max,n-min,part2);
     v.insert(v.end(),part1.begin(),part1.end());
     for(int i=0; i < p2; i++)
     {
        part2[i].push_back(min);
     }
     v.insert(v.end(),part2.begin(),part2.end());
     return p1+p2;
   }
}

void print_partition(Partition &p)
{
   for(int i=0; i < p.size(); i++) {
      cout << p[i] << ' ';
   }
   cout << "\n";
}

void print_partition_list(Partition_list &pl)
{
   for(int i = 0; i < pl.size(); i++) {
      print_partition(pl[i]);
   }
}

int main(int argc, char **argv)
{
   Partition_list v_master;

   int n = atoi(argv[1]);
   int min = atoi(argv[2]);
   int max = atoi(argv[3]);
   int count = p(min,max,n,v_master);
   cout << count << " partitions of " << n << " with min " << min  ;
   cout << " and max " << max << ":\n" ;
   print_partition_list(v_master);
}

和输出示例：

$ ./partitions 12 3 7              
6 partitions of 12 with min 3 and max 7:
6 6 
7 5 
4 4 4 
5 4 3 
6 3 3 
3 3 3 3 
$ ./partitions 50 10 20            
38 partitions of 50 with min 10 and max 20:
17 17 16 
18 16 16 
18 17 15 
19 16 15 
20 15 15 
18 18 14 
19 17 14 
20 16 14 
19 18 13 
20 17 13 
19 19 12 
20 18 12 
13 13 12 12 
14 12 12 12 
20 19 11 
13 13 13 11 
14 13 12 11 
15 12 12 11 
14 14 11 11 
15 13 11 11 
16 12 11 11 
17 11 11 11 
20 20 10 
14 13 13 10 
14 14 12 10 
15 13 12 10 
16 12 12 10 
15 14 11 10 
16 13 11 10 
17 12 11 10 
18 11 11 10 
15 15 10 10 
16 14 10 10 
17 13 10 10 
18 12 10 10 
19 11 10 10 
20 10 10 10 
10 10 10 10 10 

这篇关于算法来确定物品的可能的组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！