Распечатать оптимальное решение для алгоритма обмена монет

Question

Учитывая значение N, если мы хотим внести сдачу для N cents, и у нас есть бесконечный запас каждой из монет с номиналом S = { S1, S2, .. , Sm}, каков оптимальный способ внести сдачу для N cents.

Пример:

S = {2, 5, 10}
N = 6, then optimal solution is : 2, 2, 2

У меня рабочий код ниже:

public static void main(String argv[]) {
        long n = 10L;
        int[] combo = new int[100];
        int[] amounts = { 2, 5, 10 };
        ways(n, amounts, combo, 0, 0, 0);
    }

    public static void ways(long n, int[] amounts, int[] combo, int startIndex, int sum, int index) {
        if (sum == n) {
            printArray(combo, index);
        }

        if (sum > n) {
            return;
        }

        for (int i = 0; i < amounts.length; i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, startIndex, sum, index + 1);
            sum = sum - amounts[i];
        }
    }

    public static void printArray(int[] combo, int index) {
        for (int i = 0; i < index; i++) {
            System.out.print(combo[i] + " ");
        }
        System.out.println();
    }

Вывод:

2 2 2 2 2 
5 5 
10 

Здесь мне просто нужна оптимальная комбинация с меньшим количеством монет, поэтому только 10 в этом примере кода.

Но в этом коде используется рекурсивный подход, мое значение для N - это тип Long, так как значение N увеличивается. Я получаю stackoverflow ошибку.

Рекурсивный подход, которому я здесь следую, неверен. Как правильно решить эту проблему?

Обновление:

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

static void testcase() {
        // make int array A of size N+1
        int N = 6;
        int[] A = new int[N + 1];
        // make int array P of size N+1
        int[] P = new int[N + 1];
        // fill A[] with large value (len(S) + 1)
        int[] S = { 2, 5, 10 };
        int lengthOfS = S.length;
        for (int i = 0; i < A.length; i++) {
            A[i] = lengthOfS + 1;
        }

        A[0] = 0;

        for (int s : S) {// coin value
            for (int i = s; i <= N; i++) {
                if (A[i - s] < A[i] + 1) { // using this coin we can get better
                                            // result for sum i
                    A[i] = A[i - s] + 1;
                    P[i] = s; // write down coin for this sum
                }
            }
        }
        System.out.println(Arrays.toString(P)); // [0, 0, 2, 2, 2, 5, 2]
        System.out.println(A[N]);// 3
        int idx = N;
        for (int i = 0; i < A[N]; i++) {
            int result = idx - P[idx];
            System.out.println(result); // 4 2 0
            idx = result;
        }
    }

Этот код печатает:

[0, 0, 2, 2, 2, 5, 2]
3

4
2
0

Как исправить этот код?

Answer 1

Для фиксированного набора S = {2, 5, 10} решение довольно простое:

Нет решений для N=1,3

если N нечетное, вы должны использовать 5 - поэтому N=N-5

Теперь используйте жадный подход: получите как можно больше 10-секунд, затем как можно больше 2-х

def best(N):
    print(N, end = ":  ")
    if (N % 2):
        print("5", end = "    ")
        N = N - 5
    if N >= 10:
        print("10*", N//10, end = "    ")
        N = N % 10
    if N > 1:
        print("2*", N//2, end = "    ")

21:  5    10* 1    2* 3    
22:  10* 2    2* 1    
23:  5    10* 1    2* 4    
24:  10* 2    2* 2    

---

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

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

S = [2, 3, 5, 7, 11]
dic = {}

def rec(summ):
    if summ == 0:
        return 0
    rd = dic.get(summ)
    if rd != None:
        return rd
    minn = 9999999999999
    for s in S:
        if s <= summ:
            minn = min(minn, 1 + rec(summ - s))
    dic[summ] = minn
    return minn

N = 1000
print(rec(N))

>>92

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

Псевдокод

make int array A of size N+1
make int array P of size N+1
fill A[] with large value (MaxInt` or at least `N/min(S)) 
A[0] = 0
for s in S:  //coin value
    for (i = s; i <= N; i++)  
        if A[i - s] < A[i] + 1    //using this coin we can get better result for sum i
             A[i] = A[i - s] + 1
             P[i] = s            //write down coin for this sum

Теперь у нас есть A[N] с лучшим счетом, и мы можем получить необходимые монеты, используя последовательность P[N], P[N - P[N]]....

Рабочий Python код

S = [2, 3, 5, 7, 11]
N = 17
A = [0] + [10000] * N
P = [0] * (N + 1)
for s in S:  #coin value
    for i in range(s, N + 1):
        if A[i - s] < A[i] + 1:    #using this coin we can get better result for sum i
             A[i] = A[i - s] + 1
             P[i] = s            #write down coin for this sum

print(A) #for reference
i = N
while i > 0:
    print(P[i], end = " ")
    i = i - P[i]

>> [0, 10000, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3]
>> 11 3 3 

Примечание - если мы можем использовать каждую монету только один раз, мы должны сделать внутренний l oop в обратном направлении, чтобы избежать многократного добавления одной и той же монеты

Answer 2

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

Вот реализация на C ++
(Примечание: этот код был уже опубликовано, но я не могу найти сообщение. Вопрос удален?)

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

В коде «UP» означает, что мы будем рассматривать возможность добавления монет с более низким значением.

«DOWN» означает, что мы попытаемся уменьшить количество монет с более высоким значением.

На данном этапе мы поддерживаем массив, соответствующий количеству монет для каждого достоинства монеты

#include    <iostream>
#include    <vector>
#include    <algorithm>
#include    <numeric>

//  The order of array coins is modified

std::vector<int> get_change(std::vector<int>& coins, int amount) {
    std::vector<int> n_coins(coins.size(), 0);
    std::vector<int> n_coins_opt(coins.size(), 0);
    int n = coins.size();

    std::sort(coins.begin(), coins.end(), std::greater<int>());

    int sum = 0;    // current sum
    int i = 0;      // index of the coin being examined
    int n_min_coins = amount / coins[n - 1] + 1;
    int n_total_coins = 0;
    bool up_down = true;

    while (true) {          // UP
        if (up_down) {
            n_coins[i] = (amount - sum) / coins[i];     // max possible number of coins[i]
            sum += n_coins[i] * coins[i];
            n_total_coins += n_coins[i];
            if (sum == amount) {
                if (n_total_coins < n_min_coins) {
                    n_min_coins = n_total_coins;
                    n_coins_opt = n_coins;
                }
                up_down = false;
                sum -= n_coins[i] * coins[i];
                n_total_coins -= n_coins[i];
                n_coins[i] = 0;
                i--;
            }
            else {
                if (i == (n - 1) || (n_total_coins >= n_min_coins)) {   // premature abandon
                    sum -= n_coins[i] * coins[i];
                    n_total_coins -= n_coins[i];
                    n_coins[i] = 0;
                    up_down = false;
                    i--;
                }
                else {
                    i++;
                }
            }

        }
        else {            // DOWN
            if (i < 0) break;
            if (n_coins[i] == 0) {
                if (i == 0) break;
                i--;
            }
            else {
                sum -= coins[i];
                n_coins[i] --;
                n_total_coins--;
                i++;
                up_down = true;
            }
        }
    }

    return n_coins_opt;
}

int main() {
    std::vector<int> coins = {2, 5, 10};
    int amount = 1731;
    auto n_coins = get_change(coins, amount);

    int sum = std::accumulate (n_coins.begin(), n_coins.end(), 0);
    if (sum == 0) {
        std::cout << "no solution\n";
    } else {
        std::cout << amount << " = ";
        for (int i = 0; i < n_coins.size(); i++) {
                std::cout << n_coins[i] << "*" << coins[i] << " ";
        }
        std::cout << "\n";
    }
    return 1;
}