Проблема минимальной замены монет с ограниченным количеством монет - PullRequest
Новая
       40

Проблема минимальной замены монет с ограниченным количеством монет

0 голосов
/ 23 февраля 2019

Если быть точным, проблема заключается в следующем:
Заданный массив номиналов coins[], массив лимитов для каждой монеты limits[] и число amount, возврат минимум необходимое количество монет,чтобы получить amount, или, если это невозможно, верните ноль.Дополнительно заполните массив change номером каждой монеты, использованной в растворе.

Это мое решение: 

public static int? Dynamic(int amount, int[] coins, int[] limits, out int[] change)
    {
        int[] minCoins = new int[amount + 1];
        int[,] coinsUsedToAmount = new int[coins.Length, amount + 1];

        minCoins[0] = 1;
        for (int j = 0; j < amount; ++j)
        {
            if (minCoins[j] > 0)
            {
                for (int i = 0; i < coins.Length; ++i)
                {
                    if (coinsUsedToAmount[i, j] < limits[i])
                    {
                        int currAmount = j + coins[i];
                        if (currAmount <= amount)
                        {
                            if (minCoins[currAmount] == 0 || minCoins[currAmount] > minCoins[j] + 1)
                            {
                                minCoins[currAmount] = minCoins[j] + 1;

                                for (int k = 0; k < coins.Length; ++k) 
                                {
                                    coinsUsedToAmount[k, currAmount] = coinsUsedToAmount[k, j];
                                }
                                coinsUsedToAmount[i, currAmount] += 1;
                            }
                        }
                    }
                }
            }
        }

        if (minCoins[amount] == 0)
        {
            change = null;
            return null;
        }

        change = new int[coins.Length];
        for(int i = 0; i < coins.Length; ++i)
        {
            change[i] = coinsUsedToAmount[i, amount];
        }

        return minCoins[amount] - 1;
    }


Но в целом это не работает.

Моя проблема в том, что например в таком случае: 

amount = 141, 
coins = new int[] { 2, 137, 65, 35, 30, 9, 123, 81, 71 }                                                                                  
limits = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1 }

Оптимальное решение: 

 change = new int[] { 1, 0, 1, 1, 1, 1, 0, 0, 0 }

И мой алгоритм в результате дает ноль.Другими словами, это терпит неудачу, когда на каком-то пути вверх мне придется использовать менее оптимальное решение, чем это возможно, и тогда, в конце концов, мне не нужны монеты.
В этом примере мой алгоритм дает:
minCoins[132] = 2 (9 + 123),
Но это должно быть minCoins[132] = 4 (2 + 65 + 35 + 30), потому что тогда я могуиспользовать 9 и иметь 141 .

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

1 Ответ

0 голосов
/ 06 марта 2019

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

public static int? Dynamic(int amount, int[] coins, int[] limits, out int[] change)
{
        int[][] coinsUsed = new int[amount + 1][];
        for (int i = 0; i <= amount; ++i)
        {
            coinsUsed[i] = new int[coins.Length];
        }

        int[] minCoins = new int[amount + 1];
        for (int i = 1; i <= amount; ++i)
        {
            minCoins[i] = int.MaxValue - 1;
        }

        int[] limitsCopy = new int[limits.Length];
        limits.CopyTo(limitsCopy, 0);

        for (int i = 0; i < coins.Length; ++i)
        {
            while (limitsCopy[i] > 0)
            {
                for (int j = amount; j >= 0; --j)
                {
                    int currAmount = j + coins[i];
                    if (currAmount <= amount)
                    {
                        if (minCoins[currAmount] > minCoins[j] + 1)
                        {
                            minCoins[currAmount] = minCoins[j] + 1;

                            coinsUsed[j].CopyTo(coinsUsed[currAmount], 0);
                            coinsUsed[currAmount][i] += 1;
                        }
                    }
                }

                limitsCopy[i] -= 1;
            }
        }

        if (minCoins[amount] == int.MaxValue - 1)
        {
            change = null;
            return null;
        }

        change = coinsUsed[amount];
        return minCoins[amount];
}
...