1005 задачка, как решить??

Question

[artshelom]

Добрый день не могу понять, где ошибка в моем решении, Вот задачка
1005. Куча камней
Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
У вас есть несколько камней известного веса w1, …, wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.
Исходные данные
Ввод содержит количество камней n (1 ≤ n ≤ 20) и веса камней w1, …, wn (1 ≤ wi ≤ 100 000) — целые, разделённые пробельными символами.
Результат
Ваша программа должна вывести одно число — минимальную разность весов двух куч.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(reader.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        String text = reader.readLine();
        for (int i = 0;i<number;i++) {
            arr.add(Integer.parseInt(text.split(" ")[i]));
        }
        arr.sort(Collections.reverseOrder());
        int b = 0;
        for (Integer a:arr){
            if (b >= a){
                b -= a;
            }else{
                b += a;
            }
        }
        if (b>=0){
            System.out.println(b);
        }else{
            System.out.println(-b);
        }
    }
}

Answer 1

[Sayonji]

У вас неверный алгоритм. Пусть в куче лежат камни следующих весов: 6, 6, 4, 4, 4. Ваш алгоритм положит первые два камня в разные кучи, хотя правильный ответ (6+6)=(4+4+4).
Такую задачу нельзя решить линейно. Но её можно свести к задаче о рюкзаке: пусть S это суммарный вес камней и пусть M это решение задачи о рюкзаке для рюкзака размером S/2. Тогда ответ на вашу задачу равен S-2M.

Comments

[artshelom]

Мой алгоритм положит (6+4+4)=(6+4) - И это будет верным решением
Я подумаю как можно сделать ваше решение

[Sayonji]

artshelom: С какой стати это верное решение? У вас разница куч получилась 4, хотя если положить 6+6=4+4+4, разница будет нулевая.

[artshelom]

Sayonji: Все понял. Спасибо