2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Разбить лист на подмножества
Сообщение01.10.2020, 15:43 
Нам дан лист(множество) с числами и количество (мнимых) палочек, с помощью которых мы будем разбивать этот лист. Разбить его надо так, чтобы минимальная сумма элементов подмножества была максимальной(т. е насколько я понимаю, суммы элементов подмножеств должны быть примерно одинаковыми, #могу ошибаться). Программа выводит минимальную сумму элементов
Пример:
Ввод:
4 #количество палочек
3 2 4 4 5 7 #лист
Вывод:
7
Объяснение: чтобы минимальная сумма подмножества была максимальной расставили палочки таким образом: первую поставили в начало листа перед 3, вторую в конец листа после 7, третью палочку поставили между 4 и 4, а третью между 5 и 7.Следовательно, в таком раскладе наименьшая сумма равна 7

Получилось написать такой код для 4 палочек:
Код:
vr, t =map(int,input().split())
d=(map(int,input().split()))
sum1=d[0]
sum2= d[1]
sum3= sum(int(d[m]) for m in range(2, int(len(d))))
i=2
k=2
max = 0
for j in range(1,len(d)-1): #(1)we are increasing the distance between the second and the first stick
    while sum3 != d[len(d)-1]:#(2)(we are increasing the distance between the second and the third stick)
        sum2+=d[i]
        sum3-=d[i]
        i+=1
        a = min(sum1,sum2,sum3)
        if max < a:
            max=min(sum1,sum2,sum3)
    sum1+=d[j]
    i = k+1
    sum2=d[i-1]
    sum3=sum(int(d[m]) for m in range(i, int(len(d))))
    k += 1
print(max)

После становится понятно, что при увеличении количества палочек увеличивается количество внутренних циклов на строчках, которые я обозначила, как 1 и 2. Насколько я поняла, суммы можно запихнуть в массив и вызывать их оттуда. Но как задать зависимость между количеством циклов и количеством туристов не особо понимаю. На ум приходит только рекурсия(но разве она будет правильно работать в данном решении?) Например, записать цикл while в функцию и вызывать ее в рекурсии?

 
 
 
 Posted automatically
Сообщение01.10.2020, 15:45 
 i  Тема перемещена из форума «Программирование» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 
 
 
 Posted automatically
Сообщение04.10.2020, 15:17 
 i  Тема перемещена из форума «Карантин» в форум «Программирование»

 
 
 
 Re: Разбить лист на подмножества
Сообщение07.10.2020, 16:40 
Можно попробовать найти решение двоичным поиском.

 
 
 
 Re: Разбить лист на подмножества
Сообщение07.10.2020, 16:49 
Аватара пользователя
Либо бинпоиск по ответу, либо динамикой отвечаем на вопрос "какую максимальную сумму можно получить из первых $a$ элементов, использовав $b$ палочек".

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group