Максимальный раздел монет - PullRequest
Новая
       45

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

5 голосов
/ 09 февраля 2011

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

Учитывая систему монет со значениями v 1 , ..., v n , ограниченный запас монет a 1 , ..., a n и сумма, которую мы должны заплатить. Мы ищем алгоритм для вычисления раздела x 1 , ..., x n (с 0 <= x <sub>i <= a <sub>i ) с x 1 * v 1 + x 2 * v 2 + ... + x n * v n > = s, так что сумма x 1 + ... + x n - R (r) максимизирована, где r - это изменение, т.е. r = x 1 * v 1 + x 2 * v 2 + ... + x n * v n - s и R (r) - количество монет, возвращаемых кассиром. Мы предполагаем, что кассир имеет неограниченное количество всех монет и всегда возвращает минимальное количество монет (например, используя алгоритм жадности, описанный в SCHOENING и др.). Мы также должны убедиться, что деньги не меняются, поэтому лучшее решение - НЕ просто отдавать все деньги (потому что в этом случае решение всегда будет оптимальным).

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

1 Ответ

1 голос
/ 10 февраля 2011

Если я правильно понимаю, это в основном вариант подмножества .Если мы предположим, что у вас есть 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 из этого.Дайте мне знать, если вам нужно больше деталей.

...