用遞歸算法包裝一組盒子

我被挑戰以遞歸方式解決以下問題，但我仍然不能。用遞歸算法包裝一組盒子

問題：必須收拾所有項目從以下一組

int[] items = new int[] {4, 4, 2, 3};

到下面的框

int[] boxes = new int[] {5, 8};

目前，在算法結束時，我有

Item index: 2 
Box index: 1 
Items: 0, 0, 0, 3, 
Boxes: 1, 2, 
------------------------------------------------- 
It is possible to distribute defined set of items in given boxes.

這是不正確的，因爲有一個項目3，有兩個盒子剩餘的ca pacity 1和2.我從「||」的右邊獲得的最終積極結果是，表達。

有人能指出錯誤的代碼或推薦正確的解決方案嗎？謝謝！

我的Java代碼如下：

public class Boxes 
{ 
    public static void main(String[] args) 
    { 
     int[] items = new int[] {4, 4, 2, 3}; 
     int[] boxes = new int[] {5, 8}; 

     System.out.println(String.format("It is %spossible to distribute defined set of items in given boxes.", IsFit(items, boxes, 0, 0) ? "" : "NOT ")); 

    } 

    private static boolean IsFit(int[] items, int[] boxes, int boxIndex, int itemIndex) 
    { 
     if (boxIndex == boxes.length) 
      return false; 

     if (itemIndex == items.length) 
      return true; 

     boolean result = 
       IsFit(items, boxes, boxIndex + 1, itemIndex) 
       || 
       IsFit(items, boxes, boxIndex, itemIndex + 1) 
      ; 

     if (result) 
     { 
      int storedValue = items[itemIndex]; 

      if (boxes[boxIndex] >= storedValue) 
      { 
       boxes[boxIndex] -= storedValue; 
       items[itemIndex] = 0; 

       /* 
       System.out.println(String.format("Item index: %d", itemIndex)); 
       System.out.println(String.format("Box index: %d", boxIndex)); 

       System.out.print("Items: "); 
       for (int i : items) 
        System.out.print(String.format("%s, ", i)); 
       System.out.println(); 


       System.out.print("Boxes: "); 
       for (int b : boxes) 
        System.out.print(String.format("%s, ", b)); 
       System.out.println(); 
       System.out.println("-------------------------------------------------"); 
       */ 

       result = IsFit(items, boxes, boxIndex, itemIndex + 1); 

       items[itemIndex] = storedValue; 
       boxes[boxIndex] += storedValue; 

      } 
     } 

     return result; 

    } 
}

來源

2013-03-15 Yaugen Vlasau

你能清楚地說明實際的挑戰是什麼？ – matcheek 2013-03-15 14:17:25

是否意味着在箱子中分配物品，以便在運行結束時所有物品和箱子均爲0。還是意味着要說「不可能分發......」，因爲有物品和盒子空間仍然存在？ – ghdalum 2013-03-15 14:20:21

判斷是否有可能將所有可用項目分散到給定的框中是必要的。 – 2013-03-15 14:24:36

你的代碼很難遵循。我建議以下功能：

private static boolean fits(int[] weights, int[] boxes, int i) { 
    if (i == weights.length) 
     return true; 

    for (int j = 0; j < boxes.length; j++) { 
     if (weights[i] <= boxes[j]) { 
      boxes[j] -= weights[i]; 
      if (fits(weights, boxes, i+1)) 
       return true; 

      boxes[j] += weights[i]; 
     } 
    } 

    return false; 
}

哪些應該被稱爲

fits(items, boxes, 0);

來源

2013-03-15 14:34:55

+1在20分鐘內的好的解決方案的情況下， – 2013-03-16 22:22:40

最終posiive結果我從「||」的分辯側獲得表達。

我相信你錯了。您的最終肯定結果可能來自：

if (itemIndex == items.length) 
    return true;

當然這並不能解決整個問題。問題是（從我所能看到的）Knapsack Problem這是NP-complete的情況，您必須使用蠻力算法來解決它。

來源

2013-03-15 14:33:43 ghdalum

是的，你是對的，'||'的重要部分在<項目索引：2>，<箱子索引：1> – 2013-03-15 14:43:57

這一挑戰impressed了我很多，這就是爲什麼我張貼我的答案，雖然這個問題被接受！

private static boolean CheckTheBox(int[] a,int[] b,int i,int j) 
    {   
      i+=(a[i]==0)?1:0; 
      j+=(b[j]==0)?1:0; 

      if(i > a.length -1 || j > b.length -1) 
      { 
       return (a[a.length-1]==0 && b[b.length-1]==0)?true:false; 
      } 

      int temp=a[i]; 
      a[i]-=(a[i]!=0 && b[j]!=0)?1:0; 
      b[j]-=(b[j]!=0 && temp!=0)?1:0; 

      CheckTheBox(a,b,i,j); 

      return (a[a.length-1]==0 && b[b.length-1]==0)?true:false; 
    }

可謂是像下面，

System.out.println((CheckTheBox(items,boxes,0,0)==true?"Filled Successfully.!":"Items/Boxes Remaining.!"));

來源

2013-03-16 21:55:20

用遞歸算法包裝一組盒子

回答

相關問題