2

我目前正在开发一个java项目，我需要其中的一部分来给我一个完整的数字组合列表，
1<= A<=B<=C<=D<=E<=F<=N其中N任何整数as small as 75都将被用作输入。只要它A B C D E F可以。any integerfulfills the equality

我知道我可以简单地使用每个组合，brute force但这需要很长时间。我想做的是以一种仍然满足原始方式split的平等化为two separate平等，但它会减少几乎一半的运行。

4

2 回答 2

2

假设您想要一个满足指定条件的所有可能组合的列表A, B, C, D, E, F，那么您无法获得比蛮力回溯搜索更有效的方法。

对于 的每个可接受的值A：找到 的所有可接受的值B，然后对于每个可接受的值，找到C... 等等。

您将获得等效的运行时间：

  • 分而治之
  • 动态规划
  • 贪婪（这只是减少到回溯）

（但这些算法不适合这个问题，需要人为的实现）

于 2012-11-15T18:30:12.150 回答
0

以下将仅生成有效的有效组合。较大的 N 值可能需要一段时间，但那是因为会有大量组合满足您的不等式。

N = 75; 300500200 组合

N = 100；1609344100 组合

    for(int A = 1; A <= N ; ++A) {
        for(int B = A; B <= N; ++B) {
            for(int C = B; C <= N; ++C) {
                for(int D = C; D <= N; ++D) {
                    for(int E = D; E <= N; ++E) {
                        for(int F = E; F <=N; ++F) {
                            // do whatever you want with the combo
                        }
                    }
                }
            }
        }
    }
于 2012-11-15T18:39:29.883 回答