java - 需要加速的装箱算法

Question

我正在寻找一种智能方法来解决常见的装箱问题。给定一些具有一定容量的袋子(我这样调用它们)，以及占用一定空间的元素列表，任务是确定是否所有元素都可以放入袋子中；如果是这样，如何。我现在有一个详尽的 DFS，但它需要……永远。我的 DFS 是迭代的，需要在每一步都复制整个状态，这是非常昂贵的。这是我针对 4 个容量为 10 的袋子的特定问题的代码(如果您不想全部查看，此代码真正相关的部分只是 pack() 方法和 State 类):

import java.util.ArrayList;
import java.util.Stack;

public class BagProblem {
    int numBags;
    int bagCapacity;
    ArrayList<Item> items = new ArrayList<Item>();

    public static void main(String[] args) {
        BagProblem bp = new BagProblem(4, 10);
        bp.pack();
    }

    public BagProblem(int numBags, int bagCapacity) {
        this.numBags = numBags;
        this.bagCapacity = bagCapacity;
        items = new ArrayList<Item>();
        items.add(new Item("item0", 6));
        items.add(new Item("item1", 6));
        items.add(new Item("item2", 6));
        items.add(new Item("item5", 3));
        items.add(new Item("item6", 3));
        items.add(new Item("item7", 3));
        items.add(new Item("item8", 2));
        items.add(new Item("item9", 2));
        items.add(new Item("item10", 2));
        items.add(new Item("item11", 2));
        items.add(new Item("item12", 2));
        items.add(new Item("item13", 2));
        items.add(new Item("item14", 1));
    }

    // find a valid way to pack and print the items in each Bag, or
    // print failure
    public void pack() {
        Stack <State> s = new Stack<State>();
        Bag[] currBags = new Bag[numBags];
        for (int i = 0; i < numBags; i++) {
            currBags[i] = new Bag(bagCapacity);
        }
        s.push(new State(currBags));
        while(!s.isEmpty()) {
            State currState = s.pop();
            for (Item i : items) {
                if (!currState.containsItem(i)) {
                    State newState = new State(currState.bags);
                    newState.numItems = currState.numItems;
                    if (newState.addItem(i)) {
                        s.push(newState);
                        if (newState.numItems == items.size()) {
                            System.out.println("success");
                            System.out.println(newState);
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("failure");
    }

    private class State {
        Bag[] bags;
        int numItems;

        public State(Bag[] currBags) {
            bags = new Bag[numBags];
            for (int i = 0; i < numBags; i++) {
                bags[i] = new Bag(bagCapacity);
            }

            // figure out how to actually copy this
            for (int j = 0; j < numBags; j++) {
                Bag bagToCopy = currBags[j];
                for (Item item : bagToCopy.contents) {
                    Item newItem = new Item(item.name, item.size);
                    bags[j].size = bagToCopy.size;
                    bags[j].contents.add(newItem);
                }
            }
        }

        public boolean addItem(Item i) {
            for (Bag b : bags) {
                if (b.addItem(i)) {
                    numItems++;
                    return true;
                }
            }
            return false;
        }

        public boolean containsItem(Item i) {
            for (Bag b : bags) {
                for (Item item : b.contents) {
                    if (item.name.equals(i.name))
                        return true;
                }
            }
            return false;
        }

        public String toString() {
            String output = "";
            for (Bag b : bags) {
                for (Item j : b.contents) {
                    output += j.name + " ";
                }
                output += "\n";
            }
            return output;
        }

    }

    private class Bag {
        int capacity;
        int size;
        ArrayList<Item> contents;

        public Bag(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            contents = new ArrayList<Item>();
        }

        public boolean addItem(Item i) {
            if(size + i.size > capacity)
                return false;
            contents.add(i);
            size += i.size;
            return true;
        }

        public String toString() {
            String output = "";
            for (Item i : contents) {
                output += i.name + " ";
            }
            return output + "\n";
        }

    }

    private class Item {
        String name;
        int size;

        public Item(String name, int size) {
            this.name = name;
            this.size = size;
        }

        public String toString() {
            return name;
        }

    }
}

大约一百万年后，这确实给出了正确的答案(如果您尝试运行它，您可能不想真正等那么久):

success
item14 item7 item6 item5 
item13 item12 item2 
item11 item10 item1 
item9 item8 item0

每一行表示一个单独的包。我怎样才能加快速度？我知道有尝试将最大的项目放在第一位等的试探法，但我真正感兴趣的是获得基本的 DFS(或者我应该尝试回溯？)以减少开销；稍后我会尝试变得更漂亮。

如有任何帮助，我们将不胜感激。

Answer 1

我不使用 Java，但由于过于复杂，您的实现似乎效率很低(正如您自己提到的)。该算法本身也很奇怪，我没有尝试复制它，只是使用了明显的 O(bags^items) 蛮力算法，该算法尝试将第一个项目放入每个袋子中，对于每种情况都尝试将第二个项目放入元素放入每个袋子等...

您可以将一个项目放入袋中，而不是在堆栈上重复复制整个状态，探索具有这种变化的树的分支，然后将项目从包。

这是一个用 C# 立即完成测试用例的示例。

    static int[] itemSize;
    static int[] bagFreeSpace;
    static bool[,] doesBagContainItem; // in case this looks weird, [,] is a matrix, in java it would be [][]

    static bool pack(int item)
    { 
        // output the solution if we're done
        if (item == itemSize.Length)
        {
            for (int i = 0; i < bagFreeSpace.Length; i++)
            {
                Console.WriteLine("bag" + i);
                for (int j = 0; j < itemSize.Length; j++)
                    if (doesBagContainItem[i, j])
                        Console.Write("item" + j + "(" + itemSize[j] + ") ");
                Console.WriteLine();
            }
            return true;
        }

        // otherwise, keep traversing the state tree
        for (int i = 0; i < bagFreeSpace.Length; i++)
        {
            if (bagFreeSpace[i] >= itemSize[item])
            {
                doesBagContainItem[i,item] = true; // put item into bag
                bagFreeSpace[i] -= itemSize[item];
                if (pack(item + 1))                 // explore subtree
                    return true;
                bagFreeSpace[i] += itemSize[item];  // take item out of the bag
                doesBagContainItem[i,item] = false;
            }
        }

        return false;
    }

    static void Main(string[] args)
    {
        itemSize = new int[] { 6, 6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1 };
        bagFreeSpace = new int[] { 10, 10, 10, 10 };
        doesBagContainItem = new bool[bagFreeSpace.Length, itemSize.Length];

        if (!pack(0))
            Console.WriteLine("No solution");
    }

注意:如果你想并行执行，你需要给每个worker自己的状态副本(或每个作业1份副本)，但只有在分支点，他们仍然可以像上面一样继续，而不需要复制国家。