2

次の問題を再帰的に解決するように挑戦されましたが、まだできません。

問題: 次のセットのすべてのアイテムをパックする必要があります

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 があり、残りの容量が 1 と 2 の 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;

    }
}
4

3 に答える 3

4

あなたのコードは従うのがかなり難しいです。私は次の機能を提案します：

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-15T14:34:55.340 に答える
0

「||」のリグ側から得られる最終的なポジティブな結果 表現。

私はあなたが間違っていると信じています。あなたの最終的な肯定的な結果はおそらくこれから来るでしょう：

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

もちろん、これで問題全体が解決するわけではありません。問題は（私が見ることができることから）NP完全であるナップサック問題のケースであり、力ずくのアルゴリズムを使用してそれを解決する必要があります。

于 2013-03-15T14:33:43.497 に答える
0

この課題は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-16T21:55:20.580 に答える