
Текст задачи: у вас есть несколько камней известного веса 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 Ответы


Вот на этом тесте валится:
8 6 7 9 13 18 24 31 50
Твоя программа выдает 4, ответ 0 = 50 + 9 + 13 + 7 — 6 — 24 — 18 — 31.
Есть по этой задаче вот такое обсуждение «Две кучки камней», сама задача попроще немного, там упоминаются решения через «двоичную систему», проще говоря, перебором по вариантам раскладки камней. Для 20 камней должна успеть проходить, хотя вариантов 1М. Возможно, имеет смысл как-то оптимизировать перебор, а может, и в лоб в лимит времени влезет.