3

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

Как решить? Мне не нужен код, нужен алгоритм.

7
  • возможный дубликат ru.stackoverflow.com/questions/1274797/…
    – tohatsu
    27 июл 2022 в 12:58
  • Пожалуйста, уточните вашу конкретную проблему или приведите более подробную информацию о том, что именно вам нужно. В текущем виде сложно понять, что именно вы спрашиваете. 27 июл 2022 в 13:00
  • @tohatsu, там задача более сложная. И всё равно нет решения. Я не думаю что в таком случае можно говорить про дубликат. 27 июл 2022 в 14:36
  • 1
    Поскольку мне просто лень переписывать 7 страниц текста :), замечу просто, что это задача оптимизации, связанная с NP-полной задачей о сумме подмножества, и решается точно сия задача только за экспоненциальное время; имеется также приближенное полиномиальное решение. См. Кормен и др., "Алгоритмы. Построение и анализ. 3 изд.", раздел 35.5, стр. 1180-1186.
    – Harry
    27 июл 2022 в 15:03

3 ответа 3

4

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

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

3
  • 5
    Ваш алгоритм (8, 7, 5, 5, 5) разделит на (8, 5), (7, 5, 5). А правильный ответ (8, 7), (5, 5, 5). 27 июл 2022 в 14:31
  • Если нет ограничений на веса, то полный перебор всех подмножеств и поиск лучшего варианта. Можно оптимизировать (метод ветвей и границ). Если веса небольшие целые, то есть решение быстрее - динамическое программирование. Так или иначе - задача известная и решена сотней способов, но все решения не очень простые. :) 27 июл 2022 в 19:24
  • Давайте перейдем на следующий вопрос ru.stackoverflow.com/questions/1433746/…
    – tohatsu
    27 июл 2022 в 19:25
2
  1. Сортируем камни по весу в обратном порядке
  2. Далее в цикле по отсортированным камням кладём камень в ту кучу, вес которой на текущий момент минимален.

Пример

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

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

56, 45, 15

55, 48, 12

разница - 1 кг

4
  • 5
    Ваш алгоритм (8, 7, 5, 5, 5) разделит на (8, 5), (7, 5, 5). А правильный ответ (8, 7), (5, 5, 5). 27 июл 2022 в 14:33
  • Действительно... Ну тогда можно добавить вторую итерацию прогона: 1. Запомнили разницу кучек 2. Идём в цикле по кучке большего веса в обратном порядке: Если разница текущего камня итерации и самого лёгкого камня меньшей кучки больше или равна половине разницы кучек, то: а. меняем элементы местами. б. возвращаемся в пункт 1. Перед этим, надо проверить - достаточно ли существенна разница в весе кучек, чтобы эта итерация имела смысл. Возможно, достаточно будет условия, что разница кучек больше, чем половина самого лёгкого камня.
    – Lem0nti
    29 июл 2022 в 6:48
  • Вы придумываете эвристики, которые иногда могут помочь. Но это известная задача - задача о рюкзаке 0-1. Известный факт - для любого набора эвристик можно подобрать веса так что задача решается только полным перебором почти всех подмножеств. 29 июл 2022 в 11:37
  • "Эвристики", "иногда". Предлагаемая мной вторая итерация решает вопрос? Если нет, подскажите, пожалуйста, ситуацию когда результат будет плох. Если таковой не находится, мой вариант - рабочий алгоритм.
    – Lem0nti
    2 авг 2022 в 5:21
0

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.