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 的盒子。我从“||”右侧得到的最终肯定结果 表达。

有人可以指出错误的代码或推荐正确的解决方案吗？谢谢！

我的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 回答