我有 m 個盒子和 n 個球，每個大小不同。舉一個簡單的例子，假設我們有大小為 [10, 50, 20] 的盒子和大小為 [20, 10, 30, 10] 的球。可以解決如下，
Box 0 (Size 10) 可以存放 Ball 1 (Size 10) 或 Ball 3，但為了簡單起見，我們以 Ball 1 為例。
盒子 1（50 號）可以存放 0 號球（20 號）和 2 號球（30 號）
盒子 2（20 號）可以存放 3 號球（10 號）
為了解決這個問題，我寫了以下是使用排序和迭代方式解決的java代碼，
boolean canBallsFitInBoxes(int [] boxes, int [] balls) {
Arrays.sort(boxes);
Arrays.sort(balls);
int j = 0;
int i = 0;
for(; i < balls.length && j < boxes.length;) {
if(boxes[j] >= balls[i]){
boxes[j] -= balls[i];
i ;
} else {
j ;
}
}
return i == balls.length;
}
我測驗了幾個案例，上面的迭代解決方案有效。我可能錯過了邊緣情況，很高興聽到他們糾正它。
我自己嘗試了遞回版本，但它僅在給定陣列已經排序或框和陣列可以像（框：[10,50,20] 和球：[10,20,30,10]） . 基本上，當盒子或球的順序混亂時，我正在努力尋找使用遞回的解決方案。
但我試圖找到一種通用的方法來解決這個問題。任何建議如何在沒有顯式排序的情況下遞回地解決它？
uj5u.com熱心網友回復：
解決問題的一種強力遞回方法是取球 n 并嘗試將其放入每個盒子中。如果球適合當前框，則遞回使用下一個球，否則嘗試下一個框。
public boolean canBallsFitInBoxes(int[] boxes, int[] balls) {
return fits(boxes, balls, 0);
}
private boolean fits(int[] boxes, int[] balls, int currentBall) {
// More balls available?
if (currentBall >= balls.length)
// No -> all balls are inside boxes already -> success
return true;
// Check each box, trying to insert current ball
for (int currentBox = 0; currentBox < boxes.length; currentBox ) {
// Does ball fit into box?
if (boxes[currentBox] >= balls[currentBall]) {
// Yes -> put ball into box
boxes[currentBox] -= balls[currentBall];
// Proceed to remaining balls (recursively)
if (fits(boxes, balls, currentBall 1))
// All remaining balls fit -> success
return true;
else
// At least one of the remaining balls does not fit -> remove current ball from box again
boxes[currentBox] = balls[currentBall];
}
}
// All tries for this ball failed -> back-trace
return false;
}
如果您不喜歡遞回方法開始時的成功檢查，并且寧愿在遞回之前進行檢查，您也可以使用：
private boolean fits(int[] boxes, int[] balls, int currentBall) {
// Check each box, trying to insert current ball
for (int currentBox = 0; currentBox < boxes.length; currentBox ) {
// Does ball fit into box?
if (boxes[currentBox] >= balls[currentBall]) {
// Yes -> put ball into box
boxes[currentBox] -= balls[currentBall];
// If more balls are available, proceed to remaining balls (recursively)
if (currentBall 1 >= balls.length || fits(boxes, balls, currentBall 1))
// All remaining balls fit -> success
return true;
else
// At least one of the remaining balls does not fit -> remove current ball from box again
boxes[currentBox] = balls[currentBall];
}
}
// All tries for this ball failed -> back-trace
return false;
}
如果您不了解演算法，請隨時詢問。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/455056.html