У вас есть несколько камней известного веса. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.
Как решить? Мне не нужен код, нужен алгоритм.
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуУ вас есть несколько камней известного веса. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.
Как решить? Мне не нужен код, нужен алгоритм.
Постоянно добавляем в меньшую по весу кучу самый тяжелый камень.
Вот собственно и есть весь алгоритм.
(8, 7, 5, 5, 5)
разделит на (8, 5)
, (7, 5, 5)
. А правильный ответ (8, 7)
, (5, 5, 5)
.
27 июл 2022 в 14:31
Пример
камни: 5, 56, 45, 48, 12, 55, 15
разница - 1 кг
(8, 7, 5, 5, 5)
разделит на (8, 5)
, (7, 5, 5)
. А правильный ответ (8, 7)
, (5, 5, 5)
.
27 июл 2022 в 14:33
1. Запомнили разницу кучек 2. Идём в цикле по кучке большего веса в обратном порядке: Если разница текущего камня итерации и самого лёгкого камня меньшей кучки больше или равна половине разницы кучек, то: а. меняем элементы местами. б. возвращаемся в пункт 1.
Перед этим, надо проверить - достаточно ли существенна разница в весе кучек, чтобы эта итерация имела смысл. Возможно, достаточно будет условия, что разница кучек больше, чем половина самого лёгкого камня.
Одно из решений нашла в задачнике на https://okpython.net. Выглядит как-то просто, но для 5 камней с весом до 10 на первый взгляд выдает правильные ответы. Логика решения задачи только не совсем понятна.
# Импортируем time.
import time
# Начало выполнения программы.
start = time.time()
# Ииспользуем возможности модуля random.
from random import choice, choices
# Генерируем случайное количество камней.
n = choice(range(1, 101))
# Генерируем случайные веса камней.
w_li = choices(range(1, 1000000), k=n)
# Сортируем список по возрастанию весов.
w_li.sort()
# Начальные веса наших куч.
w_1 = 0; w_2 = 0
# Если камней четное количество.
if n%2 == 0:
# Остаточный вес примем за нуль.
w_min = 0
else:
# Удалим из списка минимальный вес,
# чтобы осталось четное число элементов,
# и сохраним его в переменной.
w_min = w_li.pop(0)
# Текущий флаг.
f = 0
# Пока список не станет пустым.
while w_li:
# Распределяем по два соседних камня
# по кучам, добавляя в одну и ту же
# кучу сперва камень с максимальным весом,
# а затем с минимальным из двух.
if f == 0:
w_1 += w_li.pop()
w_2 += w_li.pop()
f = 1
else:
w_2 += w_li.pop()
w_1 += w_li.pop()
f = 0
# Последний камень добавляем в кучу с минимальным весом.
if w_2 > w_1:
w_1 += w_min
else:
w_2 += w_min
# Выводим минимальную разность весов.
print(abs(w_2 - w_1))
# Время выполнения программы.
print('Выполнено за', time.time() - start, 'сек.')