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

[juna]

svv

А с последовательностями какой длины у Вас программа справляется? Просто интересно, всегда ли можно моим подходом получать нижнее ограничение по количеству монет, вынимаемых каждый день... Поэтому и предлагал потестить.

Что касается перебора, то может его сделать неполным. Уже говорили, что если все числа представить в двоичной системе, то задача сводится - убрать единички из всех разрядов, тогда нижнее ограничение по количеству дней - это количество двоичных разрядов самого большого числа. И понятно, что стратегия - убирать каждый день все единички из одного разряда (степени двойки) - это снимать самые большие числа из возможных, за вычетом разного рода исключений. Тогда перебор можно организовать, спускаясь именно со степеней двойки.

[deep blue]

svv Может что-то даст такое предложение:
Перебор можно сократить если использовать эффективную оценку снизу числа оставшихся дней на каждом шаге.
В качестве такой границы можно взять например:
Если осталось k различных мешочков, то число дней для их покрытия не меньше чем число дней для покрытия k различных мешочков c наборами монет 1,2,3,...,k. То есть задача свелась к классическому варианту который легко решается.

[svv]

В программе задаётся последовательность $(a_i)$ и число $m$ — желаемое количество элементов в базовом наборе. От длины последовательности время работы зависит линейно. То есть добавление одного члена почти незаметно. А вот увеличение $m$ на единицу увеличивает время на порядок и может сделать его неприемлемым...

Для ориентировки. Я взял начало Вашей первой последовательности до числа 167:
[8, 13, 16, 24, 25, 31, 39, 41, 44, 48, 57, 58, 70, 71, 80, 85, 86, 91, 92, 103, 115, 118, 122, 139, 142, 149, 151, 167]
Положил $m=7$. Программа работала 13-14 минут и выдала такие варианты:
[1, 5, 8, 10, 25, 47, 79]
[1, 5, 8, 16, 31, 41, 86]
[1, 7, 13, 15, 24, 33, 90]
[1, 8, 13, 16, 23, 41, 78]
[1, 8, 13, 16, 31, 33, 78]
[2, 6, 7, 16, 26, 36, 74]
[2, 6, 7, 16, 26, 36, 90]
[2, 6, 7, 16, 26, 52, 64]
[3, 8, 9, 13, 28, 40, 78]
[3, 8, 9, 13, 28, 54, 64]
[5, 6, 8, 10, 20, 42, 84]
[5, 6, 8, 10, 25, 47, 79]
[5, 8, 9, 15, 16, 41, 78]
[5, 8, 9, 16, 23, 33, 78]
[5, 8, 9, 16, 23, 41, 70]
[5, 8, 9, 16, 23, 41, 78]
[5, 8, 9, 16, 31, 41, 70]
[5, 8, 15, 16, 25, 42, 61]
[5, 8, 15, 16, 25, 42, 69]
[5, 8, 16, 17, 23, 33, 70]
[5, 8, 16, 17, 23, 41, 70]
[5, 8, 16, 17, 31, 41, 62]
[8, 9, 13, 16, 23, 41, 70]
[8, 9, 13, 16, 31, 41, 62]
[8, 13, 15, 16, 25, 42, 61]
[8, 13, 15, 16, 25, 42, 69]
[8, 13, 16, 17, 23, 41, 62]
Дальше я добавил к последовательности следующее число $178$. Программа работала те же 14 минут и не нашла ничего. Тем самым было показано, что для последовательности $[8,13,...,167,178]$ восемь чисел необходимы (и, конечно, достаточны, т.к. можно взять семь $b_k$, покрывающих $[8,13,...,167]$, и $b_8=178$). Следовательно, $b_8\leqslant 178$, иначе от него не будет толку.

-- Вт сен 06, 2016 14:44:03 --

deep blue
Спасибо, надо подумать.

Конечно, я реализовывал такой алгоритм, чтобы не надо было особенно напрягаться... Понятно, что он не очень эффективный.

[juna]

svv

У Вас действительно все по-честному, поскольку добавляется еще одна степень свободы - хочу вынимаю, хочу не вынимаю, даже если можно вынуть. Я же вынимаю из всех мешков, из которых это возможно. Поэтому в данном случае у вас ниже ограничения 7.383704292474053. Я же получаю на этой последовательности только за 8 дней: [88,44,22,11,5,3,1,1]. Приблизить к вашему решению, я свой алгоритм не могу, поскольку заранее не знаю, кто в кого входит.

Предлагаю потестить другие последовательности, для которых эффект сокращения теоретического ограничения не должен получаться:

[2, 6, 9, 15, 22, 23, 25, 27, 32, 33, 34, 35, 41, 44, 46, 47, 48, 52, 57, 59, 63, 65, 67, 70, 73, 76, 79, 83, 89, 93, 95, 97, 99, 103, 105, 107, 108, 109, 110, 111, 115, 118, 119, 120]
Solution:[62,30,15,7,4,2,1], [61,30,15,8,4,2,1]

[4, 6, 7, 11, 15, 16, 20, 24, 25, 26, 46, 48, 49, 50, 52, 53, 54, 57, 58, 59, 64, 65, 66, 70, 71, 72, 76, 79, 80, 82, 83, 86, 89, 90, 92, 93, 96, 101, 108, 109, 110]
Solution:[57,28,14,7,3,2,1]

[2, 3, 14, 16, 17, 18, 21, 25, 27, 28, 29, 30, 32, 35, 36, 42, 43, 57, 60, 61, 62, 66, 68, 69, 71, 73, 75, 77, 81, 83, 85, 89, 90, 91, 97, 99, 101, 103, 108]
Solution:[55,27,13,7,3,2,1]

[5, 6, 9, 11, 12, 19, 21, 22, 25, 28, 31, 33, 37, 40, 44, 45, 51, 53, 54, 56, 60, 65, 70, 75, 77, 78, 80, 89, 91, 92, 94, 96, 97, 98, 99, 100]
Solution: [53,26,13,7,4,2,1]

[2, 4, 5, 7, 8, 9, 10, 11, 17, 19, 21, 22, 24, 26, 28, 35, 37, 38, 44, 47, 49, 50, 57, 59, 61, 62, 66, 68, 69, 72, 74, 75]
Solution: [39,20,10,5,3,1,1]

Точность алгоритма зависит от параметра, и я не уверен, что выбирал ее всегда оптимально. Поэтому в первом случае предложил 2 решения. На последнем наборе может быть сокращение и соответственно результаты не сойдутся.

[Masik]

Напомню условие, а то много времени прошло, пока удалось найти быстрый алгоритм.

Цитата:

Имеется $N$ мешков с монетами. Каждый день разрешается взять из одного или нескольких мешков по одинаковому числу монет.
За какое минимальное число дней $M$ можно взять все монеты?

Пусть $i$-й мешок содержит $a_i$ монет. Без ограничения общности можно считать, что все $a_i$ попарно различны, $a_1 < a_2 <\dots< a_N$.
С первого взгляда напрашивается рекурсивное решение: выбрать величину очередной взятки $b_i$ и подмножество мешков, к которым взятка применяется, тем самым сведя задачу к аналогичной, но меньшего размера. Но при таком подходе образуется совершенно неподъёмный перебор, в котором ещё и не просматриваются какие-либо эффективные отсечения.
Совершенно другой способ перебора предложил svv. Он упорядочил взятки по неубыванию: $b_1 \leqslant b_2 \leqslant\dots\leqslant b_M$ и доказал очень эффективное ограничение сверху на размер $i$-й взятки. Кроме того, svv предложил оценку числа требуемых дней снизу. Перебор стал обозримым.
Если развить идею svv, увеличив влияние оценки числа требуемых дней снизу на отсечения ветвей перебора, то задача совсем упрощается.

(Алгоритм)

Алгоритм
$Mmax = \min(N, \log_2{a_N}) + 1$.
Запомнить тривиальное решение.

Для каждого веса $w$ от $a_1$ до 1 по убыванию
{
Положить $b_1 = w$.
Выбрать вторую и последующие взятки.
Если ОТСЕЧЕНИЕ, прервать цикл.
}

====================
Выбор $m$-й и последующих взяток (рекурсивная процедура)

Если оценка снизу числа взяток не меньше Mmax, вернуть ОТСЕЧЕНИЕ.

Узнать наименьший непокрываемый мешок, пусть n.

Если все мешки покрыты,
{
Положить $Mmax = m-1$.
Запомнить решение.
Вернуть УСПЕХ.
}

Для каждого веса $w$ от $a_n$ до $b_{m-1}$ по убыванию
{
Положить $b_m = w$.
Выбрать $m+1$-ю и последующие взятки.
Если ОТСЕЧЕНИЕ, прервать цикл.
}

Вернуть НЕУДАЧА.

====================
Вычисление оценки снизу числа взяток для вектора $b_1...b_m$

Повторять
{
Пусть $n$ - наименьшее, при котором $a_n > \sum\limits_{i=1}^{m}{b_i}$.
Если такого мешка нет, вернуть $m$.
Иначе, положить $b_{m+1} = a_n$.
}

Я удалил из множества мешков повторения и добавил мешок весом 1024 (чтобы тривиальный алгоритм давал 11 взяток). Для поиска решения для 10 взяток и доказательства, что решений с девятью взятками нет, потребовались доли секунды. Однопоточная программа на С++ работала на стареньком компьютере IE5. При этом в дереве перебора было исследовано всего 99643 узла, что смехотворно мало для такой задачи.
0 сек. 11 взятий: $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$.
0 сек. 10 взятий: $ 8, 12, 13, 16, 18, 32, 64, 136, 252, 485$.

Для другого примера, когда в качестве множества мешков были взяты первые 100 квадратов, программа тоже работала доли секунды и выдала следующий результат.
0 сек. 14 взятий: $ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192$.
0 сек. 13 взятий: $ 1, 4, 9, 16, 36, 64, 144, 256, 289, 575, 1244, 2496, 5120$.
0 сек. 12 взятий: $ 1, 4, 9, 15, 36, 80, 160, 320, 640, 1280, 2560, 5120$.

[svv]

Masik
Я восхищён. Надо будет переписать опять на C++ и попробовать.
Мне бы такую целеустремлённость, я бы уже на Марс слетал.

[juna]

Спасибо, Masik. Я тоже посмотрю на досуге.

Кстати, справедливости ради, следует упомянуть, что уважаемый svv прислал мне расчеты предлагаемых выше последовательностей в личной переписке, и для своего алгоритма я действительно обнаружил, что он минимизирует сумму $\sum_{i=1}^M{b_i}$ (в ваших обозначениях). Например, для последовательности из 100 квадратов чисел, он дает такое решение:
Верхнее ограничение: 13.28771237954945
День: 1 Количество монет: 4828
День: 2 Количество монет: 2498
День: 3 Количество монет: 1293
День: 4 Количество монет: 669
День: 5 Количество монет: 346
День: 6 Количество монет: 179
День: 7 Количество монет: 92
День: 8 Количество монет: 47
День: 9 Количество монет: 24
День: 10 Количество монет: 12
День: 11 Количество монет: 6
День: 12 Количество монет: 3
День: 13 Количество монет: 2
День: 14 Количество монет: 1

Что дает сумму: 4828+2498+1293+669+346+179+92+47+24+12+6+3+2+1=10000 (хотя не уверен, что и это предел мечтаний);

У Вас же даже при меньшем количестве слагаемых: 1+4+9+15+36+80+160+320+640+1280+2560+5120=10225.

Т.е. отсюда выплывает еще одна модификация формулировки:
при фиксированном $M$ обеспечить минимум $K=\sum_{i=1}^M{b_i}\rightarrow\min$

(например, вольная формулировка: над каждым мешком стоит осьминожка с не более чем $K$ щупальцами, одна щупальца вынимает один камень и отпадает. Сколько щупалец нужно по минимуму дать осьминожкам? )

[kknop]

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

Для другого примера, когда в качестве множества мешков были взяты первые 100 квадратов, программа тоже работала доли секунды и выдала следующий результат.
0 сек. 12 взятий: $ 1, 4, 9, 15, 36, 80, 160, 320, 640, 1280, 2560, 5120$.

Интересно, а если взять не 100, а 1000 квадратов, то всё равно в оптимальном результате будет последовательное удвоение, начавшееся с числа 80, или же началом удвоения будет уже что-то другое?

[juna]

kknop в сообщении #1161309 писал(а):

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

Для другого примера, когда в качестве множества мешков были взяты первые 100 квадратов, программа тоже работала доли секунды и выдала следующий результат.
0 сек. 12 взятий: $ 1, 4, 9, 15, 36, 80, 160, 320, 640, 1280, 2560, 5120$.

Интересно, а если взять не 100, а 1000 квадратов, то всё равно в оптимальном результате будет последовательное удвоение, начавшееся с числа 80, или же началом удвоения будет уже что-то другое?

Это скорее всего одно из решений за 12 дней, поэтому, что там происходят удвоения не столь интересно. Интересно именно среди всех найти с минимальной суммой взяток из одного мешка за каждый день и там наблюдать закономерности.

[Masik]

kknop в сообщении #1161309 писал(а):

Интересно, а если взять не 100, а 1000 квадратов, то всё равно в оптимальном результате будет последовательное удвоение, начавшееся с числа 80, или же началом удвоения будет уже что-то другое?

Для слабо возрастающих последовательностей обычно имеем много оптимальных решений. Выгодно искать лексикографически наибольшее из них, поэтому тенденция выхода хвоста последовательности на удвоения, действительно, наблюдается, но не всегда. Для квадратов от 1 до 1000 решение ниже.

0 сек. 20 взятий: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, сумма: 1048575.
305 сек. 19 взятий: 1, 4, 9, 16, 36, 64, 140, 260, 520, 1040, 2080, 4215, 8320, 16900, 33540, 67600, 133900, 268580, 526760, сумма: 1063985.
Открыто узлов поиска: 50362.

[grizzly]

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

0 сек. 20 взятий: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,

А зачем в этом наборе 2? (Наверное, я не понял задачу.)

[grizzly]

Да нет, вроде всё правильно понял. Очевидно, что для квадратов справедлива оценка сверху от Shadow за вычетом двойки в первой степени (а как же её использовать для квадратов-то?!):

Shadow в сообщении #1148368 писал(а):

но за $\lceil\log_2{n}\rceil$, где n - мешок с наибольшим числом монет, независимо от числа мешков, можно.

[juna]

Ага. Двойку можно смело выкинуть и взять за те же 19 дней: [1, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288].
Это видимо по инерции верхнее ограничение степеней двойки в программе сработало (которое не верхнее лексикографически) ...

[juna]

А вообще решающие последовательности, как было замечено, обладают большим люфтом и остаются таковыми, если начиная с какой-то ее части все последующие числа просто заменить последовательным удвоением последнего числа ее части. Например, для суммы 100 первых квадратов получили такую последовательность: [4872, 2501, 1285, 659, 337, 172, 87, 44, 22, 11, 5, 3, 1, 1] (немного другая, чем была приведена, но также с суммой 10000). Берем и, например, с числа 337, все последующие заменяем удвоением: [5392,2696,1348,674,337,172, 87, 44, 22, 11, 5, 3, 1, 1] - она также остается решающей, а если от последовательности вообще почти ничего не оставить - начать с 3: [6144, 3072, 1536, 768, 384, 192, 96, 48, 24, 12, 6, 3,1,1], то нам и последний день не понадобится, т.е. решающей станет [6144, 3072, 1536, 768, 384, 192, 96, 48, 24, 12, 6, 3,1], сокращая количество дней на 1.

[Masik]

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

Что дает сумму: 4828+2498+1293+669+346+179+92+47+24+12+6+3+2+1=10000 (хотя не уверен, что и это предел мечтаний);

Если сумма будет меньше 10000, то последний мешок (в котором 10000 монет) опустошить не удастся.
А для 12 дней минимальная сумма 10021.
12 взятий: 1, 4, 8, 16, 36, 80, 160, 320, 640, 1280, 2596, 4880, сумма: 10021.
12 взятий: 1, 4, 8, 16, 36, 80, 160, 320, 640, 1280, 2516, 4960, сумма: 10021.
12 взятий: 1, 4, 8, 16, 36, 80, 160, 320, 640, 1280, 2436, 5040, сумма: 10021.
И других вариантов нет.

-- 21.10.2016, 07:06 --

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

Да нет, вроде всё правильно понял. Очевидно, что для квадратов справедлива оценка сверху от Shadow за вычетом двойки в первой степени (а как же её использовать для квадратов-то?!):

Shadow в сообщении #1148368 писал(а):

но за $\lceil\log_2{n}\rceil$, где n - мешок с наибольшим числом монет, независимо от числа мешков, можно.

Оценка Shadow не совсем верна. Но и в алгоритме опечатка, две первые строки алгоритма должны быть такими:
$Mmax = \min(N, \left\lfloor\log_2{a_N}\right\rfloor + 1)$.
Запомнить тривиальное решение.

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