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



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

}

}

4

4 回答 4

1

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

为了更简单地解释这个场景，考虑随机生成 5 个数字。伪代码应该如下所示。

  1. 生成5个随机数，R1, R2 ... R5
  2. 总计 = 这 5 个随机数的总和。
  3. 为所有项目生产
    • 产生1 = R1/总数；// 产生[i] = R[i]/total;
于 2013-08-28T17:12:46.517 回答
0

请不要使用嵌套的 for 循环那么深！改用递归：

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。尝试生成所有这些可能性绝对没有意义（并且需要永远计算）。

于 2013-08-28T17:22:01.060 回答
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 次循环终止条件。因此，除了“if”条件检查 101^12 次之外，您在“for”循环中进行了 102^12 次条件检查，因此总共进行了 2.4e24 次条件检查。

在我的解决方案（基于组合）中，对于外部 12 个循环，for 循环检查的次数减少到 6.243e15，
并且如果条件检查 = 6.243e15。现在，对于每个真正的“if”条件，for 循环的数量（即内部 12 个 for 循环）是 12^12 = 8.9e12。假设条件有 x 个为真。所以总条件检查

=没有内部for循环*x

= 8.9e12 * x + 6.243e15

我无法找到 x 的值。但是，我相信它不足以使总条件检查大于 2.4e24

于 2013-08-28T18:00:40.107 回答
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遍历参数中的所有位并返回1s 的数量。如果这不是 5，那么就跳过这个迭代，因为你说你最多只想要 5 个混合。（有792个这样的案例）。

该j循环从 0:100 开始循环遍历 4 个（不是 5 个）项目的所有组合。有 100^4 个这样的案例。

内部循环遍历所有 12 个变量，对于那些在 1 中的位位置为 1 的变量，i这意味着您正在使用该变量。您可以通过从 中获取接下来的两位小数来计算百分比j。对于第 5 项 ( cnt==5)，您不取数字，您通过从 100 中减去来计算它。

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

于 2013-08-28T20:06:53.410 回答