Подскажите алгоритм

Question

Есть задача: У вас есть несколько камней известного веса. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной. Даже не представляю, как решить. Не подскажете, как это можно сделать? Мне не нужен код, нужен алгоритм. Спасибо!

Answer 1

Постоянно добавляем в меньшую по весу кучу самый тяжелый камень.

Вот собственно и есть весь алгоритм.

Answer 2

Сортируем камни по весу в обратном порядке
Далее в цикле по отсортированным камням кладём камень в ту кучу, вес которой на текущий момент минимален.

Пример

камни: 5, 56, 45, 48, 12, 55, 15

Сортировка - 56, 55, 48, 45, 15, 12
Цикл приведёт к такому варианту:

56, 45, 15

55, 48, 12

разница - 1 кг

Answer 3

Одно из решений нашла в задачнике на 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, 'сек.')

БЛОГ НА HUSL

Подскажите алгоритм

Ответы (3 шт):

56, 45, 15

55, 48, 12