DjangoBB LoFi version

Начало » Python для новичков » Задачка на камни.

NiG

Авг. 9, 2019 14:43:40

Прошу помочь додуматься как решить)
У вас есть несколько камней известного веса w1, …, wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.
Исходные данные
Ввод содержит количество камней n (1 ≤ n ≤ 20) и веса камней w1, …, wn (1 ≤ wi ≤ 100 000) — целые, разделённые пробельными символами.
Результат
Ваша программа должна вывести одно число — минимальную разность весов двух куч.

 def sum_list(arr):
	sum=0
	for i in arr:
		sum+=i
	return sum
qty = int(input())
stone1=[]
stone2=[]
L=[int(input()) for i in range(qty)]
L = sorted(L)
L.reverse()
for i in range(len(L)):
	if sum_list(stone1)<sum_list(stone2):
		stone1.append(L[i])
	else:
		stone2.append(L[i])
print(stone1,'\n')
print(stone2)
sum_ = abs(sum_list(stone1)-sum_list(stone2))
print(sum_)

Пробовал с разными данными, на кучи делит правильно, но попробовал сделать с такими: 6,6,4,4,4. Делит на (6,4) и (6,4,4), а должно быть (6,6) и (4,4,4).

FishHook

Авг. 9, 2019 15:46:32

NiG
Я не проверял на большом количесве входных данных, попробуйте вот этот вариант, может быть он будет лучше

   
data = [1, 2, 3, 4, 5, 6, 8]
data.sort()
chunk1 = []
chunk2 = []
first, last = 0, len(data) - 1
while first <= last:
    small, big = data[first], data[last]
    if sum(chunk1) <= sum(chunk2):
        chunk1.append(small)
        first += 1
    else:
        chunk2.append(big)
        last -= 1
print chunk1, "=", sum(chunk1)
print chunk2, "=", sum(chunk2)

Striver

Авг. 9, 2019 16:32:28

Жадный поиск в таких задачахдалеко не всегда находит лучший вариант.
Ограничение на количество в 20 камней позволяет провести полный пребор всех комбинаций (при 20-ти камнях получается 1048574 итераций).

 from random import randint
from itertools import combinations
ВСЕГО_КАМНЕЙ = 20
МАССЫ_КАМНЕЙ = [randint(1, 100000) for номер in range(ВСЕГО_КАМНЕЙ)]
 
def поиск(массы_камней):
    полная_масса = sum(массы_камней)
    половина_массы = полная_масса/2
    текущая_разница = полная_масса
    лучшая_комбинация = []
    итерация=0
    for размер_выборки in range(1, len(массы_камней)):
        for комбинация in combinations(массы_камней, размер_выборки):
            итерация += 1
            if abs(половина_массы - sum(комбинация)) < текущая_разница:
                лучшая_комбинация = комбинация
                текущая_разница = abs(половина_массы - sum(комбинация))
    print("Массы всех камней:", массы_камней)
    print("Всего итераций:", итерация)
    print("Лучшая комбинация:", лучшая_комбинация)
    print("Минимальная разность:", текущая_разница*2)
    
поиск(МАССЫ_КАМНЕЙ)

результат:

Массы всех камней: [23416, 96577, 30371, 28914, 72502, 54875, 60542, 88126, 94719, 48998, 22536, 91681, 94437, 69805, 27082, 11177, 76937, 70229, 4410, 87610]
Всего итераций: 1048574
Лучшая комбинация: (23416, 96577, 30371, 28914, 72502, 88126, 48998, 91681, 69805, 27082)
Минимальная разность: 0.0

Прикольно, что при количестве ровно в 20 камней (и, видимо, при любом достаточно большом чётном) минимальная разность при случайных массах всегда очень маленькая.

AD0DE412

Авг. 9, 2019 23:56:59

 import random
col = int(input())
rock = [random.randint(1, 100000) for i in range(col)]
rock.sort()
rock.reverse()
half_mass = int(sum(rock) / 2)
part = [rock[0]]
for i in rock[1:]:
    if sum(part + [i]) <= half_mass:
        part.append(i)
#набрать 1 часть (part), все что не в ней вторая часть
print(rock, part, sum(part), half_mass, half_mass - sum(part))

ps в условии еще нужно обработать последнию каменюку(решить стоит ли ее добовлять в кучу, или нет, что бы было болие ровно распределена масса. но чет лень, спать хочу

)
pss в общем тесты показали что эээ… вариант выше (от Striver) точнее

NiG

Авг. 10, 2019 17:04:47

Спасибо всем!

ZiG

Авг. 13, 2019 09:42:10

Смотрел видео про алгоритмы, и были полные задачи… Много вариантов решения было, но все не точный… Единственный вариант, который точный - полный перебор всех вариантов. Striver - тут полностью прав.