Максимальный раздел монет

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

Для монетной системы со значениями v1,...,vn ограниченный запас монет a1,...,a n и сумму s, которую нам нужно заплатить. Мы ищем алгоритм для вычисления разбиения x1,...,xn (с 0‹=xi‹= ai) с x1*v1+x2*v2 +...+xn*vn >= s такое, что сумма x1+...+xn - R(r) максимизируется, где r - изменение, т.е. r = x1*v1+x2 *v2+...+xn*vn - s, а R(r) - количество монет, возвращенных кассиром . Мы предполагаем, что кассир имеет неограниченное количество всех монет и всегда возвращает минимальное количество монет (например, используя жадный алгоритм, описанный в SCHOENING et al.). Мы также должны убедиться, что деньги не размениваются, так что лучшим решением будет НЕ просто отдать все деньги (потому что в этом случае решение всегда будет оптимальным).

Спасибо за ваш творческий вклад!


algorithm data-partitioning greedy
person Treecj    schedule 09.02.2011    source источник
comment
Принадлежит cstheory   -  person bobobobo    schedule 09.02.2011
comment
Если у вас всегда с собой минимально возможное количество монет (если вы раньше играли в эту игру каждый раз в супермаркете), то вы можете рассчитать его, используя подход отдачи всех своих монет, а затем подсчитать, что будет возвращено, и вычесть это. изменение от ваших текущих вещей.   -  person eumiro    schedule 09.02.2011
comment
@bobobobo Я не думаю, что это будет считаться вопросом исследовательского уровня, это довольно распространенная проблема и не подходит для cstheory.   -  person Kiril    schedule 09.02.2011
comment
Какой у вас номинал монет? Таковы ли они, что жадный алгоритм внесения сдачи всегда дает минимальное количество монет?   -  person IVlad    schedule 10.02.2011
comment
@eumiro: Да, я тоже наткнулся на это решение, но пока не уверен, хватит ли его на все случаи (особенно если кассир может вернуть меньше для суммы s+1, чем для s)...   -  person Treecj    schedule 10.02.2011
comment
@IVlad: Система монет не обязательно должна быть «дружественной к жадности», но я думаю, мы должны предположить, что это так..   -  person Treecj    schedule 10.02.2011

Ответы (1)


arrow_upward
1
arrow_downward

Если я правильно понимаю, это в основном вариант суммы подмножества. Если мы предположим, что у вас есть по 1 каждой монете (a[i] = 1 для каждой i), то вы решите это следующим образом:

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
        sum[j] |= sum[j - v[i]]

Затем найдите первое k >= s, а sum[k] равно true. Вы можете получить фактические использованные монеты, отслеживая, какая монета внесла вклад в каждый sum[j]. Чем ближе вы сможете получить свою сумму к s, используя свои монеты, тем меньше будет сдача, а это то, что вам нужно.

Теперь у вас нет по 1 каждой монеты i, у вас есть a[i] каждой монеты i. Я предлагаю это:

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
       for k = 1 to a[i] do
           if j - k*v[i] >= 0 do
               sum[j] |= sum[j - k*v[i]] <- use coin i k times

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

person IVlad    schedule 09.02.2011
comment
Большое спасибо @IVlad - очень хорошее решение и хорошее объяснение! На самом деле у меня тоже была где-то в голове проблема с подмножеством, но я не нашел с ней решения. Остается только один вопрос: можем ли мы всегда быть уверены, что решение с наименьшими изменениями является правильным? Возможно ли, что существует раздел, в котором у нас больше сдачи, но в итоге меньше монет, чем в решении с минимальной сдачей? Я думаю о сдаче 4 цента, для которой требуется как минимум 2 монеты (2x2), тогда как для сдачи 5 центов требуется только 1 монета... - person Treecj; 10.02.2011
comment
@ Тоби - это правда, хороший улов. Чтобы исправить это, вам нужно будет повторить k с s на maxSum и для каждого sum[k] = true запустить алгоритм минимального количества монет для алгоритма сдачи на k - s и сохранить этот минимум. Я понимаю, что это не очень эффективно, но пока это все, что у меня есть. Я еще немного подумаю и дам вам знать, если я смогу придумать что-нибудь получше. - person IVlad; 10.02.2011