задача по программированию timus online judge №1005, python

314 просмотра
0
0 Комментариев

Текст задачи: у вас есть несколько камней известного веса w1, …, wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.

n = int(input())
s = input()
new = s.split(' ')
A = []
sum_ = 0
for i in new:
    A.append(int(i))
    sum_ = sum_ + int(i)
A = sorted(A)
include = [0] * n
l_len = n
r_len = 0
l_sum = sum_
r_sum = 0
diff_before = sum_
while True:
    if l_sum > r_sum:
        for i in range(n-1):
            if include[i] == 0 and abs((l_sum - A[i]) - (r_sum + A[i])) < abs(l_sum - r_sum):
                include[i] = 1
                l_sum -=A[i]
                r_sum += A[i]
    elif r_sum > l_sum:
        for i in range(n-1):
            if include[i] == 1 and abs((r_sum - A[i]) - (l_sum + A[i])) < abs(l_sum - r_sum):
                include[i] = 0
                r_sum -=A[i]
                l_sum += A[i]
    diff_after = abs(l_sum - r_sum)
    if diff_before == diff_after or diff_after == 0:
        break
    elif diff_after < diff_before:
        diff_before = diff_after
a = int(abs(l_sum - r_sum))
print(a)

Смысл программы примерно такой:
для каждого камня из большей кучи:
переложить в меньшую число, если разница куч сократится
иначе ничего не делать
если разница куч после цикла сократилась, то повторить цикл.
Из всех тестов, что я пробовал, программа дает правильный ответ,а при проверке на timus результат не верный. В чем здесь может быть ошибка?
Пробовал выполнить программу методом DP: создавал таблицу n * максимальное_число, но по времени не проходило решение


Добавить комментарий

1 Ответы

Python Опубликовано 14.12.2018
0

Вот на этом тесте валится:

8
6 7 9 13 18 24 31 50

Твоя программа выдает 4, ответ 0 = 50 + 9 + 13 + 7 — 6 — 24 — 18 — 31.

Есть по этой задаче вот такое обсуждение «Две кучки камней», сама задача попроще немного, там упоминаются решения через «двоичную систему», проще говоря, перебором по вариантам раскладки камней. Для 20 камней должна успеть проходить, хотя вариантов 1М. Возможно, имеет смысл как-то оптимизировать перебор, а может, и в лоб в лимит времени влезет.

Добавить комментарий
Напишите свой ответ на данный вопрос.
Scroll Up