我在面試時遇到了這個問題，似乎無法思考如何解決它。我還沒有找到任何解釋其背后邏輯的教程。
使用函式ArrayChallenge(arr)，獲取存盤在arr其中的整數陣列，其中始終包含偶數個整數，并確定如何將它們拆分為兩個偶數集合，然后回傳第一個集合的字串表示，然后是每個整數的第二個集合用逗號分隔，兩個集合按升序排序。先行的集合是第一個整數最小的集合。
例如，如果 arr 是 [16,22,35,8,20,1,21,11]，那么你的程式應該輸出 1,11,20,35,8,16,21,22
[16,22,35,8,20,1,21,11] 總和 = 134
1,11,20,35 之和 = 67 8,16,21,22 之和 = 67
兩個陣列的大小也等于 arr.length /2
uj5u.com熱心網友回復：
問題不需要按時間順序編碼。制定一個集中程式來解決這個背包問題，但不要編碼。然后對結果進行排序，并給出結果。
現在如果你解決失敗，比如超時，仍然有一個方法完成。
問題可以進一步簡化，通過使用陣列的和arr，將其除以 2，然后搜索這個半和的子陣列。
這個問題提出了一些奇怪的限制：arr保持偶數個值 (8)，兩個結果陣列應該具有相同的偶數個值（均為 4）。
選擇第 i個值所屬的子陣列是二進制的。
所以從一個排序的陣列開始，當達到一半時切割解決方案。
您可以從 00001111（位 1 的一半）開始，這可能太大了，接下來的位將是 00010111, 00011011, 00011101, 00011110, 00101110, ...
更容易的可能是簡單的遞回，計數高達一半：
// Array arr sorted decreasingly to have less values to try out.
boolean solve(Set<Integer> selectedNumbers, int selectedSum, int index) {
if (selectedNumbers.size() >= arr.length/2) {
return sum == arrSum/2;
}
if (index > arr.length) {
return false;
}
boolean solved = false;
// First case: add array element at this index:
if (selectedSum arr[index] <= arrSum/2) {
seplectedNumbers.add(arr[index]);
arrSum = arr[index];
solved = solve(selectedNumbers, arrSum, index 1);
if (!solved) {
// No remove(int index), so remove an Object, Integer.
selectedNumbers.remove(Integer.valueOf(arr[index]));
arrSum -= arr[index];
}
}
// Second case: do not add array element at this index:
if (!solved) {
solved = solve(selectedNumbers, arrSum, index 1);
}
return solved;
}
以上當然是蠻力解決方案。如果您從事運籌學，您可能會發現這些數字的分布開始（如提到的位）。但是需要時間，對我來說，我微薄的數學知識會阻止這一點。解決后，如果您知道更快的解決方案，您可能會發表評論。
uj5u.com熱心網友回復：
這個答案在精神上與Joop Eggen 的答案相似。它實作了檢查兩者的（短小）優化selectedTotal 和 discardedTotal若超過目標（注意，這個假設所有值為正中止的一個分支;如果不是這種情況下，最小的值，說x < 0，你只必須添加-x到所有值，運行演算法，并-x從答案中減去）。
輸出與原始帖子中指定的完全相同 - 由于它僅在找到完整解決方案時生成，因此此代碼應該比不斷添加和洗掉部分答案的值的演算法更快，例如 Joop's (selectedNumbers.add其次是selectedNumbers.remove當結果不起作用時；集合操作可能很快，但不執行它們甚至更快！）。
public class Main {
public static boolean search(int[] values, int goal, int index,
int selectedTotal, int discardedTotal,
List<Integer> selected, List<Integer> discarded) {
if (selected.size() == values.length/2 &&
discarded.size() == values.length/2) {
return selectedTotal == goal;
}
if (selectedTotal > goal ||
discardedTotal > goal ||
index == values.length) {
return selectedTotal == goal;
}
// try selecting value at index ...
if (selected.size() < values.length/2 &&
search(values, goal, index 1,
selectedTotal values[index], discardedTotal,
selected, discarded)) {
selected.add(values[index]);
return true;
}
// ... and, if that did not work, try discarding value at index
if (discarded.size() < values.length/2 &&
search(values, goal, index 1,
selectedTotal, discardedTotal values[index],
selected, discarded)) {
discarded.add(values[index]);
return true;
}
return false;
}
public static List<Integer> solve(int[] values) {
Arrays.sort(values);
int goal = IntStream.of(values).sum() / 2;
List<Integer> selected = new ArrayList<>();
List<Integer> discarded = new ArrayList<>();
if ( ! search(values, goal, 0,
0, 0, selected, discarded)) {
throw new IllegalArgumentException("This puzzle cannot be solved");
}
Collections.reverse(selected);
Collections.reverse(discarded);
selected.addAll(discarded);
return selected;
}
public static void main(String[] args) {
System.out.println(solve(new int[] {16,22,35,8,20,1,21,11}));
}
}
uj5u.com熱心網友回復：
您將使用迭代并首先遍歷陣列。然后你做2個整數。在每個迭代周期中，首先檢查 integer1 是否大于 integer2。然后將一個數字放入 array1 并將其值添加到 integer1。重復。如果 int1 大于 int2，則將其放入 array2 并將值添加到 int2。最后，對陣列進行排序就大功告成了。這就是我將如何解決它。這行得通嗎？我真的很感興趣。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/324143.html