Форум программистов [Powered by Invision Power Board]

Цитата(Stolzen @ 10.8.2012, 12:19

)

Необходимо выбрать элементы из P так, чтобы количество элементов было минимальным, а сумма цен элементов была больше или равна W. Если вариантов несколько, выбрать тот, который ближе к W.

Цитата(Stolzen @ 10.8.2012, 13:39

)

Что скажете?

Код


public class Sum {
    //основная точка входа
    public static Result find(final List<Integer> elements, final int minSum) {
        if (elements.isEmpty()) //если элементов нету
            return null; //нету решений
        Collections.sort(elements); //сортируем элементы по возрастанию
        return findInSortedArray(elements, minSum); //основная функциональность
    }

    //требование - элементы отсортированы и количество элементов больше нуля. minSum - это W в вашем описании
    public static Result findInSortedArray(final List<Integer> elements, final int minSum) {
        int index = Collections.binarySearch(elements, minSum); //поиск элемента
        if (index >= 0) //если нашли
            return new Result(elements.get(index)); //возвращаем его как результат

        int upperBoundIndex = -index - 1; //элемент не найден, здесь индекс элемента, который больше чем minSum (может указывать за пределы множества, если большего элемента нету)
        if (upperBoundIndex == 0) //элементов меньше чем minSum нету
            return new Result(elements.get(upperBoundIndex)); //возвращаем первый, больший чем minSum, элемент

        List<Integer> leftElements = elements.subList(0, upperBoundIndex); //создается подмножество элементов, которое содержит только элементы, которые меньше minSum
        Result leftResult = findBestSum(leftElements, minSum); //поиск решения для подмножества
        Result rightResult = null;
        if (upperBoundIndex != elements.size()) //существует элемент, который больше minSum
            rightResult = new Result(elements.get(upperBoundIndex)); //создаем решение на основе большего элемента

        return Result.getBetter(rightResult, leftResult); //выбираем лучший вариант
    }

    //требование - элементы отсортированы, количество элементов больше нуля и среди элементов, нету элементов больше minSum
    public static Result findBestSum(List<Integer> elements, final int minSum) {
        Result result = null;

        while (true) {
            int lastIndex = elements.size() - 1;
            int lastValue = elements.get(lastIndex);
            elements = elements.subList(0, lastIndex); //создается подмножество элементов, которое не содержит последний элемент
            if (elements.isEmpty()) //если подмножество пусто
                break; //выходим

            Result subResult = findInSortedArray(elements, minSum - lastValue); //поиск решения для подмножества без последнего элемента, и W = minSum - <значение последнего элемента>
            if (subResult == null) //решенией нет
                break; //выходим (их уже и не будет, т.к. массив отсортирован)

            Result newResult = new Result(subResult, lastValue); //Формируем решение на основе решения для подмножества. Result = {<Result для подмножества>, lastValue}. lastValue - удаленные элемент из подмножества

            result = Result.getBetter(result, newResult); //выбираем лучшее решение между текущим и вновь посчитанным.
        }

        return result;
    }
}

Код


public class Result {
    private final List<Integer> elements;
    private final int sum;
    
    public Result(int oneElement) {
        this.elements = Collections.singletonList(oneElement);
        this.sum = oneElement;
    }

    public Result(Result subResult, int newValue) {
        this.elements = new ArrayList<>(subResult.elements);
        this.elements.add(newValue);
        this.sum = subResult.getSum() + newValue;
    }

    public int get(int index) {
        return elements.get(index);
    }
    public int size() {
        return elements.size();
    }
    public int getSum() {
        return sum;
    }

    public static Result getBetter(Result left, Result right) {
        if (right == null)
            return left;
        if (left == null)
            return right;
        if (left.getSum() < right.getSum())
            return left;
        if (left.getSum() > right.getSum())
            return right;
        if (left.size() > right.size())
            return right;
        return left;
    }
}

Цитата(Stolzen @ 10.8.2012, 16:03

)

близость к сумме конечно приоритетнее, чем количество элементов.

Цитата(Akina @ 13.8.2012, 13:30

)

Где математическое определение критерия оптимальности?

Цитата(Akina @ 13.8.2012, 13:30

)

если нужна сумма 98, она не набирается, а набирается 99 из 11 элементов или 100 одним элементом - какой вариант выбрать?

Цитата(Stolzen @ 13.8.2012, 09:28

)

А можно на словах описать, что тут происходит?

Цитата(Stolzen @ 13.8.2012, 09:28

)

У меня вот такая реализация для алгоритма выше получилась.

Код


P = {50, 20, 30}
W = 50
Result = {50}

P = {10, 20}
W = 5
Result = {10}

P = {5, 10, 30}
W = 20
Result = {30}

P = {40, 50, 80}
W = 65
Result = {80}

P = {10}
W = 80
Result = null

P = {10, 20}
W = 40
Result = null

P = {10, 15, 20}
W = 30
Result = {10, 20}

P = {10, 20, 30, 41}
W = 50
Result = {20, 30}

P = {1, 2, 23, 30, 50}
W = 53
Result = {23, 30}

Цитата(Stolzen @ 13.8.2012, 14:14

)

Меня, по правде, больше интересовали подходы к решению подобных задач.

Цитата(Stolzen @ 13.8.2012, 14:14

)

У меня нет такого, извините.

Цитата(Akina @ 13.8.2012, 21:59

)

Ну здесь Вы собсно имеете в чистом виде задачу об одномерном раскрое. И решаете её соответственно. Либо какой-то точный переборный метод, скажем метод ветвей и границ, либо (если устраивает решение, близкое к оптимуму, а необязательно оптимум) генетика.

Цитата(Akina @ 13.8.2012, 21:59

)

А вот это очень плохо. Вы обязаны иметь... ммм... ну, скажем, функцию, в которую Вы передаёте два решения, а она возвращает ответ, какое из них лучше. Иначе решать задачу не получится. Ощущения класса "склоняюсь к" не программируются.

Цитата(korian @ 13.8.2012, 18:11

)

Можете проверить ваш алгоритм на таких данных (я их использовал для своих тестов и это вроде как основные моменты, которые надо проверить):

Цитата(korian @ 13.8.2012, 18:11

)

Я добавил комментарии.

Цитата(Stolzen @ 14.8.2012, 12:28

)

Почитаю про одномерный раскрой

Цитата(Stolzen @ 14.8.2012, 10:28

)

Да, теперь немного понятнее. Получается, примерно такая же идея, как в посте 2, только алгоритм реализован эффективнее?

Цитата(Stolzen @ 14.8.2012, 10:28

)

У этого алгоритма есть какое-нибудь название?