Bin Packing (Поиск ответов по четырем группам)

Question

Я пишу программу упаковки бина в одном измерении.Я хочу только одну возможную корзину.Таким образом, он не включает в себя много бен его только один.Эта программа только ищет группы квадратов и взрывается, если группы квадратов не равны номеру поиска.Я хочу обыскать каждую возможную группу, которая больше четырехугольников.Например, у нас есть 60 60 50 40 45 35 25 15, и мы ищем суммирование, равное 180, и ответ равен 60 60 45 15, это хорошо, но если мы ищем 250, это не будет работать.Вы можете мне помочь?Это ссылка на программу https://github.com/omerbguclu/BinPacking1D Это код алгоритма. O массив - это числа, массив - это расположение ответов

    public BinPacking() {

}

public void binpack(ArrayList<Integer> o, ArrayList<Integer> a, int wanted) {
    int sum = 0;
    if (wanted > 0) {
        control(o, a, wanted);
        if (is) {
            return;
        }
        for (int i = 0; i < o.size(); i++) {
            sum += o.get(i);
            summing(o, a, wanted - sum, i + 1);
            if (is) {
                a.add(i);
                return;
            }
            for (int j = i; j < o.size(); j++) {
                if (i != j) {
                    sum += o.get(j);
                    summing(o, a, wanted - sum, j + 1);
                    if (is) {
                        a.add(i);
                        a.add(j);
                        return;
                    }
                    sum -= o.get(j);
                }
            }
            sum -= o.get(i);
            // "/////////////*******************////////////////////");
        }
        if (wanted != sum) {
            System.out.println("There is not an answer with quad summing method");
        }
    }

}

public void summing(ArrayList<Integer> o, ArrayList<Integer> a, int wanted, int loop) {
    int sum = 0;
    if (loop < o.size() && wanted > 0) {
        for (int i = loop; i < o.size(); i++) {
            if (wanted == o.get(i)) {
                a.add(i);
                is = true;
                return;
            }
            for (int j = loop; j < o.size(); j++) {
                if (i != j) {
                    sum = o.get(i) + o.get(j);
                    if (wanted != sum) {
                        sum = 0;
                    } else {
                        a.add(i);
                        a.add(j);
                        is = true;
                        return;
                    }

                }
                // System.out.println("///////////////////////////////////");
            }
        }
        System.out.println("There is not an answer with binary summing method");
    }
}

public void control(ArrayList<Integer> o, ArrayList<Integer> a, int wanted) {
    for (int i = 0; i < o.size(); i++) {
        if (o.get(i) == wanted) {
            a.add(i);
            is = true;
            break;
        }

    }

}

Answer 1

Существует довольно хорошо отлаженный и эффективный механизм для получения всех возможных комбинаций набора объектов.По сути, вы рассматриваете членство в комбинации как BitSet, которое представляет, входит ли каждый член набора в комбинацию.Тогда посещение каждой комбинации - это просто посещение каждой BitSet комбинации.

Вот как я стараюсь ее реализовать:

public class Combo<T> implements Iterable<List<T>> {

    private final List<T> set;

    public Combo(List<T> set) {
        this.set = set;
    }

    public Iterator<List<T>> iterator() {
        BitSet combo = new BitSet(set.size());
        return new Iterator<List<T>>() {
            public boolean hasNext() {
                return combo.cardinality() < set.size();
            }

            public List<T> next() {
                int i = 0;
                while (combo.get(i))
                    combo.clear(i++);
                combo.set(i);
                return combo.stream().mapToObj(set::get).collect(Collectors.toList());
            }
        };
    }
}

Таким образом, ваше решение станет:

for (List<Integer> combo: new Combo<>(...)) {
    if (combo.size >= 4 && combo.stream.reduce(0, Integer::sum) == total)
        ....
}

Хакерская версия той же идеи:

for (long l = 0; l < 1 << (input.size() - 1); l++) {
    List<Integer> combo = BitSet.valueOf(new long[]{l}).stream()
            .mapToObj(input::get).collect(Collectors.toList());
    if (combo.stream().mapToInt(n -> n).sum() == total) {
        System.out.println(combo);
    }
}