logo标签列表

Java中生成全部和为100的12个数字组合的高效方法

javaalgorithmmathpermutationtime-complexity
3
我在混合厂有12种产品（称为a-l），需要产生不同的百分比，总和显然要达到100％。下面的代码很简单，但效率非常低。是否有更有效的算法？
*编辑：如下面所述，有太多的可能性要计算，无论是否高效。我将把这个问题改为只有最多5种或12种产品混合物，并针对从12种产品中选择5种产品的方式运行它。
有Python代码，您们中的一些人已经指出了如何计算组合的可能性。但是我的Python很少（即0％），你们中的某人能用Java术语解释一下吗？我可以在Java中获得组合（http://www.cs.colostate.edu/~cs161/Fall12/lecture-codes/Subsets.java）
public class Main {


public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {


   for(int a=0;a<=100;a++){
        for(int b=0;b<=100;b++){
             for(int c=0;c<=100;c++){
                 for(int d=0;d<=100;d++){
                     for(int e=0;e<=100;e++){
                          for(int f=0;f<=100;f++){
                                for(int g=0;g<=100;g++){
                                   for(int h=0;h<=100;h++){
                                       for(int i=0;i<=100;i++){
                                            for(int j=0;j<=100;j++){
                                               for(int k=0;k<=100;k++){
                                                      for(int l=0;l<=100;l++){

                                                    if(a+b+c+d+e+f+g+h+i+j+k+l==100)

                                                      {

                                            System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+g+" "+h+" "+i+" "+j+" "+k+" "+l);



       }}}}}}}}}}}}}

}

}

2
我在想这段代码怎么会产生 FileNotFoundException 和 UnsupportedEncodingException 异常。 - devnull
1
也许这会有帮助：http://en.wikipedia.org/wiki/Knapsack_problem - NeplatnyUdaj
1
并不是我支持12个嵌套循环... for(int b=0;b<=100-a;b++) for(int c=0;c<=100-a-b;c++) ... （或类似的代码） - Bernhard Barker
3
据我统计，假设顺序重要，将12个数字相加得到100的方法大约有四万亿种。你确定需要逐一尝试吗？ - Kevin
不幸的是，一些参数，如闪点/粘度是非线性的，而Excel的求解器使用牛顿法时，会找到局部最小值而不是成本的全局最小值。因此，我现在想尝试采用蛮力方法。Groovy：是的，它们可以具有相同的百分比。只要总和为100，它们也可以为0。 - 0idani0
显示剩余8条评论
4个回答
1

为什么要把它搞得这么难。想简单的方法。

为了更简单地解释情景，考虑生成 5 个随机数。伪代码应该像下面这样。

  1. 生成 5 个随机数，R1、R2... R5
  2. total = 这 5 个随机数之和。
  3. 对于所有要生成的项目
    • produce1 = R1/total; // produce[i] = R[i]/total;
生成随机数如何保证所有组合？您能详细说明一下吗？ - 0idani0
对于“独立概率”，它应该遵循三个规则，以上都做得很好。您可能需要谷歌搜索“概率的三个基本规则”。 - Kowser
应该易于理解。 - Kowser
有什么原因导致了你的踩？至少我可以改进自己。 - Kowser
0
请不要使用嵌套循环，而是使用递归代替：
public static void main(String[] args) {
    int N = 12;
    int goal = 100; 

    generate(N, 0, goal, new int[N]);
}

public static void generate(int i, int sum, int goal, int[] result) {
    if (i == 1) {
        // one number to go, so make it fit
        result[0] = goal - sum;
        System.out.println(Arrays.toString(result));
    } else {
        // try all possible values for this step
        for (int j = 0; j < goal - sum; j++) {
            // set next number of the result
            result[i-1] = j;
            // go to next step
            generate(i-1, sum + j , goal, result);
        }
    }
}

请注意，我只测试了N = 3和goal = 5。尝试生成所有这些可能性绝对没有意义（而且需要很长时间来计算）。
该算法违反了所需的概率约束条件。在计算最后一项时出现错误。最后一项并非随机选择。 - Kowser
但递归肯定是这个问题更优雅的解决方案。 - user2577094
@Kowser，在确定性算法中根本没有概率的存在。我生成了所有可能的分布，这与OP的代码是等价的。你能指出在哪里提到我们需要随机均匀地生成一个解吗？ - Vincent van der Weele
0
for(int a=0;a<=100;a++){
    for(int b=0;b<=50;b++){
         for(int c=0;c<=34;c++){
             for(int d=0;d<=25;d++){
                 for(int e=0;e<=20;e++){
                      for(int f=0;f<=17;f++){
                            for(int g=0;g<=15;g++){
                               for(int h=0;h<=13;h++){
                                   for(int i=0;i<=12;i++){
                                        for(int j=0;j<=10;j++){
                                           for(int k=0;k<=10;k++){
                                                  for(int l=0;l<=9;l++){

                                                if(a+b+c+d+e+f+g+h+i+j+k+l==100)

                                                  {

                                                // run 12 for loops for arranging the  
                                                // 12 obtained numbers at all 12 places      


   }}}}}}}}}}}}}

在原始方法（基于排列）中，迭代次数为102^12 = 1.268e24。即使第102次迭代是错误的，它也会检查第102次循环终止条件。因此，在“for”循环中有102^12个条件检查，除了“if”条件检查101^12次，总共有2.4e24个条件检查。
在我的解决方案（基于组合），外部12个循环的for循环检查数量减少到6.243e15，而if条件检查数量为6.243e15。现在，每个真实的“if”条件的内部12个for循环的数量为12^12 = 8.9e12。假设有x个真实的if条件，则总条件检查量为
= 内部for循环次数 * x
= 8.9e12 * x + 6.243e15
我无法找到x的值。但是，我相信它不会足够大，以至于总条件检查次数大于2.4e24。
但是你不能让前11个产品的百分比为0，而第12个产品的百分比为100%吗？ - Seth Moore
抱歉，答案不正确，我已经进行了编辑。请现在检查。 此外，a、b、c...的范围是100/1、100/2、100/3...& 100/12。 - Sumedh
0

假设你的评论是每个组合只能有5个元素，其他7个为0％。试试这个：

for (i = 0; i < (1<<12); ++i) {
    if (count_number_of_1s(i) != 5) { continue; }
    for (j = 0; j < 100000000; ++j) {
       int [] perc = new int[12];
       int val = j;
       int sum = 0;
       int cnt = 0;
       for (k = 0; k < 12; ++k) {
         if (i & (1 << k)) {
            cnt++;
            if (cnt == 5) {
              perc[k] = 100 - sum;
            }
            else {
              perc[k] = val % 100;
              val /= 100;
            }
            sum += perc[k];
            if (sum > 100) { break; }
         }
         else { perc[k] = 0; }
       }
       if (sum == 100) {
         System.out.println(perc[0] + ...);
       }
    }
}

外层循环遍历使用12个物品的所有可能组合。您可以通过循环遍历1:2^12中的所有数字来实现此操作，该数字的二进制表示中的1是您正在使用的元素。count_number_of_1s是一个函数，它循环遍历参数中的所有位并返回1的数量。如果这不是5，则跳过此迭代，因为您说您最多只想混合5个。（有792种这样的情况）。

j循环遍历0:100中4（而不是5）个项目的所有组合。有100^4种这样的情况。

内部循环遍历所有12个变量，并且对于那些在i中的位位置上有1的变量，这意味着您正在使用该变量。通过从j中取下两个小数位来计算百分比。对于第5个项目（cnt==5），您不需要取数字，而是通过从100中减去得出。

这将需要很长时间（几分钟），但不会像12个嵌套循环那样糟糕。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接