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

Ответ 1

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

В вашем случае измените рекурсивную функцию 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

Ответ 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);
    }
}

Ответ 3

Просто добавьте шаг memoization к рекурсивному решению, и динамический алгоритм попадает прямо из него. Следующий пример приведен в 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

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

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 выше немного длиннее вашего.

Ответ 4

В общем случае, когда значения монет могут быть произвольными, проблема, которую вы представляете, называется проблемой ранца и, как известно, принадлежит 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)) приводит к вычислениям различных количество умножений и сложений. То есть один метод является более оптимальным (более быстрым), чем другой метод. Динамическое программирование - это мотив, который сводит в таблицу вычислительные затраты различных методов и выполняет фактические вычисления в соответствии с графиком (или программой), динамически вычисляемым во время выполнения.

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

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

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

Ответ 5

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

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

Ответ 6

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

(более подробную информацию можно найти в моем блоге @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];
        }

Ответ 7

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

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;
}