Emballage d'un ensemble de boîtes avec un algorithme récursif

Question

J'ai été mis au défi de résoudre le problème suivant de manière récursive, mais je ne le peux toujours pas.

Le problème: Il est nécessaire d'emballer tous les éléments de ce qui suit mis

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

dans les cases suivantes

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

Au moment, à la fin de l'algorithme je

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. 

Ce qui n'est pas correct, car il y a un élément 3 et il y a deux boîtes avec ca restant pacité 1 et 2. Le résultat positif final que je reçois du côté droit du "||" expression.

Quelqu'un pourrait-il indiquer le mauvais code ou recommander une bonne solution? Merci!

Mon code java est ci-dessous:

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; 

    } 
} 

Answer 1

Votre code est assez difficile à suivre. Je propose la fonction suivante:

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; 
} 

qui devrait être appelé comme

fits(items, boxes, 0); 

Answer 2

Le résultat posiive finale, je reçois du côté du Rigth "||" expression.

Je crois que vous vous trompez. Votre résultat positif final vient probablement de ceci:

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

Bien sûr, cela ne résout pas tout le problème. Le problème est (de ce que je peux voir) un cas de Knapsack Problem qui est NP-complete et vous devez le résoudre en utilisant un algorithme de force brute.

Answer 3

Ce défi a impressed moi beaucoup, c'est pourquoi je suis annonce ma réponse si cette question a été acceptée.!

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; 
    } 

peut être appelé comme ci-dessous,

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