Алгоритм упаковки в корзину нуждается в ускорении

Я ищу разумный способ подойти к варианту распространенной проблемы с упаковкой в ​​мусорное ведро. Учитывая количество сумок (как я их называю) определенной вместимости и список предметов, занимающих определенное пространство, задача состоит в том, чтобы определить, все ли предметы могут поместиться в сумки; и если да то как. Прямо сейчас у меня работает исчерпывающий 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 (или, может быть, мне следует попробовать вернуться?), чтобы иметь меньше накладных расходов; Позже постараюсь покрасивее.

Любая помощь будет принята с благодарностью.