2

该练习是一个简单的具有挑战性的 Java 程序。输入包含：

  1. 数组“n”的大小，
  2. 数组 A 的输入和
  3. 另一个大小为“n-1”的数组 B 的输入
  4. “finalsum”是数组 A 中所有元素的总和

打印将数组 A 中的所有元素相加以达到最终总和的正确顺序的最正确算法是什么，即“finalsum”，这样我们就可以避免对数组 B 中的任何值求和。

Inputs: (split to three lines for clarity)

1. 

3             //n, the size of the array
2 4 6         //array a of size n
4 8           //array b of size n-1

//finalsum = 2 + 4 + 6 = 12. Similarly for the 2nd input

Output: 0 1 2 (or) 2 1 0 is also correct
        but 1 0 2 is wrong because it cannot add up to 4, since 4 is present in the array b 

2. 

20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191

Output: 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 (or) many other ways too
4

2 回答 2

1

您的算法可能如下所示：

  1. 取一个元素A
  2. 将元素添加到当前总和。检查当前总和是否包含在B
  3. 如果当前总和在 中B，则跳到中的下一个元素A
  4. 如果当前总和不在 中B，则递归以从中选择下一个元素A（删除当前元素）。
  5. 当所有元素A都被选择后，返回索引作为解决方案备份堆栈。
  6. 如果 的所有元素A都在没有解决方案的情况下进行了测试，并且我们目前处于递归堆栈的最顶层，则可以得出结论，没有解决方案。

这些步骤中的大多数应该相对简单地实施。

于 2013-10-16T19:34:11.757 回答
0

why can't we use the modified form of all permutation algorithm, where check for the sum in each step. if the current sum is equal to any element in B (for this we can use hash map) then don't proceed else proceed.

Hope i am clear.

Thanks.

于 2013-10-16T19:42:33.680 回答