Модификация старой задачи про мешки с монетами

[juna]

Masik в сообщении #1161524 писал(а):

Если сумма будет меньше 10000, то последний мешок (в котором 10000 монет) опустошить не удастся.

Ну вот и предел мечтаний

Интересно, для тривиального количества дней для всех последовательностей можно спуститься до суммы, равной количеству монет в последнем мешке? (похоже, что да)

-- Пт окт 21, 2016 08:28:40 --

Masik в сообщении #1161524 писал(а):

И других вариантов нет.

А это полный перебор?

[grizzly]

Masik в сообщении #1161524 писал(а):

Понятно, что тривиальное решение не обязано быть оптимальным и учитывать особенности данных.

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

У каждого свой интерес в этой задаче. Меня немного удивляет, что для 100 квадратов нашлось решение, лучше тривиального, а для 1000 -- нет.
А что можно ожидать при дальнейшем увеличении числа квадратов? Логично предположить, что дельта между тривиальным и идеальным решениями будет расти, а асимптотической разницы не будет. Или нет?

[grizzly]

Подрихтовал интуицию, теперь ничего не удивляет.
Нет, дельта вряд ли будет нарастать. Шансы случайно оторваться хороши вначале, когда квадраты и удвоения растут с примерно одинаковой скоростью. Дальше шансов намного меньше.

[Masik]

juna в сообщении #1161532 писал(а):

А это полный перебор?

Это исчерпывающий перебор с описанными отсечениями. Просто условие в алгоритме было изменено, чтобы он искал все решения, а не одно.

grizzly в сообщении #1161564 писал(а):

Меня немного удивляет, что для 100 квадратов нашлось решение, лучше тривиального, а для 1000 -- нет.

В диапазон от $2^{13} = 8192$ до $2^{14} - 1 = 16383$ попадают квадраты чисел от 91 до 127. Для квадратов чисел от 91 до 101 есть решение за 12 взяятий, а для остальных - нет. Решений с 11 взятиями нет.
В диапазон от $2^{19} = 524288$ до $2^{20} - 1 = 1048575$ попадают квадраты чисел от 725 до 1023. Для квадратов чисел от 725 до 812 есть решение за 18 взяятий, а для остальных - нет. Решений с 17 взятиями нет.
Будет ли с ростом числа мешков возрастать дельта, сомнительно.