Динамическое программирование - решение об изменении монет

Question

Я рассматриваю некоторые старые заметки из моего курса по алгоритмам, и проблемы с динамическим программированием кажутся мне немного сложными. У меня проблема в том, что у нас неограниченный запас монет с некоторыми номиналами x1, x2, ... xn, и мы хотим внести изменения для некоторого значения X. Мы пытаемся разработать динамическую программу, чтобы решить, может ли изменение для X быть сделано или нет (не сводя к минимуму количество монет, или возвращая, какие монеты, только правда или ложь).

Я немного подумал над этой проблемой, и я вижу рекурсивный способ сделать это, когда это что-то вроде ...

MakeChange(X, x[1..n this is the coins])
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
            return true;
    }
    return false;

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

Answer 1

Ваш код - хорошее начало.Обычный способ преобразовать рекурсивное решение в динамическое программирование - это сделать его «снизу вверх» вместо «сверху вниз».То есть, если ваше рекурсивное решение вычисляет что-то для определенного X, используя значения для меньшего x, тогда вместо этого вычислите то же самое , начиная с при меньшем x, и поместите его в таблицу.

Inв вашем случае измените рекурсивную функцию MakeChange на таблицу canMakeChange.

canMakeChange[0] = True
for X = 1 to (your max value):
   canMakeChange[X] = False
   for i=1 to n:
     if X>=x[i] and canMakeChange[X-x[i]]==True: 
       canMakeChange[X]=True

Answer 2

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

import java.util.ArrayList;
import java.util.List;

public class CoinDenomination {

    int denomination[] = new int[]{50,33,21,2,1};
    int minCoins=Integer.MAX_VALUE;
    String path;

    class Node{
        public int coinValue;
        public int amtRemaining;
        public int solutionLength;
        public String path="";
        public List<Node> next;

        public String toString() { return "C: "+coinValue+" A: "+amtRemaining+" S:"+solutionLength;}
    }

    public List<Node> build(Node node)
    {
        if(node.amtRemaining==0)
        {
            if (minCoins>node.solutionLength) {
                minCoins=node.solutionLength;
                path=node.path;
            }
            return null;
        }

        if (node.solutionLength==minCoins) return null;
        List<Node> nodes = new ArrayList<Node>();
        for(int deno:denomination)
        {
           if(node.amtRemaining>=deno)
           {
               Node nextNode = new Node();
               nextNode.amtRemaining=node.amtRemaining-deno;
               nextNode.coinValue=deno;
               nextNode.solutionLength=node.solutionLength+1;
               nextNode.path=node.path+"->"+deno;
               System.out.println(node);
               nextNode.next = build(nextNode);
               nodes.add(node);

           }
        }

        return nodes;
    }

    public void start(int value)
    {
        Node root = new Node();
        root.amtRemaining=value;
        root.solutionLength=0;
        root.path="start";
        root.next=build(root);
        System.out.println("Smallest solution of coins count: "+minCoins+" \nCoins: "+path);
    }

    public static void main(String args[])
    {
        CoinDenomination coin = new CoinDenomination();
        coin.start(35);
    }
}

Answer 3

Вот версия c # только для справки, чтобы найти минимальное количество монет, необходимое для данной суммы:

(можно обратиться к моему блогу @ http://codingworkout.blogspot.com/2014/08/coin-change-subset-sum-problem-with.html для более подробной информации)

public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum)
        {
            coins.ThrowIfNull("coins");
            coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
            sum.Throw("sum", s => s <= 0);
            int[][] DP_Cache = new int[coins.Length + 1][];
            for (int i = 0; i <= coins.Length; i++)
            {
                DP_Cache[i] = new int[sum + 1];
            }
            for(int i = 1;i<=coins.Length;i++)
            {
                for(int s=0;s<=sum;s++)
                {
                    if (coins[i - 1] == s)
                    {
                        //k, we can get to sum using just the current coin
                        //so, assign to 1, no need to process further
                        DP_Cache[i][s] = 1;
                    }
                    else 
                    {
                        //initialize the value withouth the current value
                        int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s];
                        DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I;
                        if ((s > coins[i - 1]) //current coin can particiapte
                            && (DP_Cache[i][s - coins[i - 1]] != 0))
                        {
                            int noOfCoinsUsedIncludingCurrentCoin_I = 
                                DP_Cache[i][s - coins[i - 1]] + 1;
                            if (minNoOfCounsWithoutUsingCurrentCoin_I == 0)
                            {
                                //so far we couldnt identify coins that sums to 's'
                                DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I;
                            }
                            else
                            {   
                                int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I, 
                                    minNoOfCounsWithoutUsingCurrentCoin_I);
                                DP_Cache[i][s] = min;
                            }
                        }
                    }
                }
            }
            return DP_Cache[coins.Length][sum];
        }

Answer 4

Эта статья очень актуальна: http://ecommons.library.cornell.edu/handle/1813/6219

По сути, как уже говорили другие, оптимальное изменение, составляющее произвольный X с произвольными наборами наименований, является NP-Hard, то есть динамическое программирование не даст своевременного алгоритма. В этой статье предлагается алгоритм полиномиального времени (то есть полиномиальный по размеру входных данных, что является улучшением по сравнению с предыдущими алгоритмами) для определения того, всегда ли жадный алгоритм выдает оптимальные результаты для данного набора номиналов.

Answer 5

В общем случае, когда значения монет могут быть произвольными, представляемая вами проблема называется Проблема с ранцем и, как известно, относится к NP-полной ( Pearson, D. 2004 ), поэтому поэтому не разрешима в полиномиальное время, такое как динамическое программирование.

Возьмите патологический пример: x [2] = 51, x [1] = 50, x [0] = 1, X = 100. Затем требуется, чтобы алгоритм «рассмотрел» возможности внесения изменений с помощью монеты. x [2], альтернативно внося изменения, начиная с x [1]. Первый шаг, используемый с национальной чеканкой, иначе известный как алгоритм жадности - до , «используйте самую большую монету меньше рабочего итога», не будет работать с патологическими чеканками , Вместо этого такие алгоритмы испытывают комбинаторный взрыв, который превращает их в NP-завершенные.

Для некоторых специальных схем размещения монет, таких как практически все в фактическом использовании, включая фиктивную систему X [i + 1] == 2 * X [i], существуют очень быстрые алгоритмы, даже O (1) в выдуманном случае, чтобы определить лучший результат. Эти алгоритмы используют свойства значений монет.

Мне не известно о динамическом программном решении, которое использует преимущества оптимальных подрешения, как того требует мотив программирования. В общем случае проблема может быть решена с помощью динамического программирования только в том случае, если она может быть разложена на подзадачи, которые при оптимальном решении могут быть преобразованы в решение, которое доказуемо оптимально. То есть, если программист не может математически продемонстрировать («доказать»), что перекомпоновка оптимальных промежуточных решений задачи приводит к оптимальному решению, то динамическое программирование не может быть применено.

Примером, обычно приводимым для динамического программирования, является приложение для умножения нескольких матриц. В зависимости от размера матриц выбор можно оценить A · B · C в качестве одной из двух эквивалентных форм: ((* A · B ) · C ) или ( A · ( B · C )) приводит к расчеты разного количества умножений и сложений. То есть один метод является более оптимальным (более быстрым), чем другой метод. Динамическое программирование - это мотив, который сводит в таблицу вычислительные затраты различных методов и выполняет фактические вычисления в соответствии с графиком (или программа ), вычисленным динамически во время выполнения.

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

Номенклатуру «динамическое программирование» можно сравнить с «линейным программированием», в котором «программа» также используется в значении «планировать».

Чтобы узнать больше о динамическом программировании, обратитесь к величайшей книге об алгоритмах, известных мне до сих пор, «Введение в алгоритмы» Кормена, Лизерсона, Ривеста и Стейна. «Ривест» - это «R» «RSA» и динамическое программирование - это всего лишь одна из десятков глав.

Обложка рекомендуемой книги. http://ecx.images -amazon.com / изображения / I / 41hJ7gLDOmL._SL500_AA300_.jpg

Answer 6

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

cache = {}
def makeChange(amount, coins):
    if (amount,coins) in cache:
        return cache[amount, coins]
    if amount == 0:
        ret = True
    elif not coins:
        ret = False
    elif amount < 0:
        ret = False 
    else:
        ret = makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])
    cache[amount, coins] = ret
    return ret

Конечно, вы можете использовать декоратор для автоматического запоминания, что приводит к более естественному коду:

def memoize(f):
    cache = {}
    def ret(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return ret
@memoize
def makeChange(amount, coins):
    if amount == 0:
        return True
    elif not coins:
        return False
    elif amount < 0:
        return False
    return makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])

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

Answer 7

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

int memory[#(coins)]; //initialize it to be -1, which means hasn't been calculated
MakeChange(X, x[1..n this is the coins], i){
    if(memory[i]!=-1) return memory[i];
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i], i) ){
            memory[i]=true;
            return true;
        }
    }
    return false;
}