2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Максимальная нажива
Сообщение17.09.2011, 11:46 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
В $i$-ой куче лежит $s_i$ камней, $i=1, \cdots, n$. Если я найду кучу с номером $i,$ в которой камней больше, чем в куче с номером $i+1,$ то я перекладываю один камень из кучи $i$ в кучу $i+1.$ За такое перекладывание мне платят 1 золотую монету, поэтому я высматриваю, где бы ещё можно переложить камень. И так далее. Хочется заработать как можно больше. Предложите стратегию.

 Профиль  
                  
 
 Re: Максимальная нажива
Сообщение17.09.2011, 12:59 
Заслуженный участник
Аватара пользователя


14/02/07
2648
Кагбе понятно, что стратегия такая: сначала переложить все, что можно, из $n-1$ в $n$. Затем из $n-2$ в $n-1$. Затем снова из $n-1$ в $n$. Затем снова из $n-2$ в $n-1$. Когда нечего уже перекладывать, то из из $n-3$ в $n-2$. И так далее. Доказать оптимальность пока не могу.

 Профиль  
                  
 
 Re: Максимальная нажива
Сообщение19.09.2011, 22:46 


03/10/10
102
Казахстан
Хорхе, может индукцией?
Для начала отметим, что по вашей стратегии, в итоге последняя куча имеет наибольшее(может одно из наибольших) количество камней среди всех куч, иначе нашлась куча которая имеет макс камней, т.е. мы не закончили операции, а по стратегии мы, как говорится, делаем до талого.
Допустим для k эта стратегия верна, покажем что и для k+1 она действует. Иметь монеты с k+1 кучи мы можем только перебрасывая камни с k в k+1, т.е. обеспеча маскимумом камнями k-ую кучу, мы поимеем максимум монет с k+1-ой, а применяя стратегию к первым k кучам, мы обеспечиваем максимум камнями k-ую кучу, т.е. обеспечиваем максимальную выгоду с k+1 кучи, а в совокупности со всех куч.

Верно ли? Или я ошибся?

 Профиль  
                  
 
 Re: Максимальная нажива
Сообщение21.09.2011, 08:30 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Simba в сообщении #484307 писал(а):
Допустим для k эта стратегия верна, покажем что и для k+1 она действует.
В какую сторону она действует?
Заработать меньше, чем по этой стратегии, у меня никак не получается! :mrgreen:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group