در این مسئله که اینجا طرح می شود، هدف آن است که پیدا کنیم به چند روش می توان مقداری پول را با سکه هایی مشخص، خورد کرد (تبدیل کرد).

داشته های ما مقدار پولی که باید خورد شود و نوع سکه ها برای این کار است؛ و می بایست الگوریتمی طراحی کنیم که با این داده ها، تمام حالت های مختلف خورد کردن پول با سکه های تعیین شده را شمارش و گزارش کند.

در این مطلب سعی ما بر آن است که علاوه بر نشان دادن راه حل هایی برای مسئله خورد کردن پول، برتری برنامه ریزی پویا بر بازگشتی را نمایان کنیم.

مثال زیر را در نظر بگیرید:

Amount = 5

coins [] = {1,2,3}

Ways to make change = 5

{1,1,1,1,1} {1,1,1,2}, {1,2,2}, {1,1,3} {2,3}

روش های حل

الف) راه حل بازگشتی

ما به شیوه ای بازگشتی می توانیم این مسئله را حل کنیم. راه حل ما به این شکل است که ما یا یک سکه را برای خورد کردن باقی مانده پول استفاده می کنیم یا آن را در آن مرحله (آن فراخوانی) کنار می گذاریم. سپس برای هر کدام از این دو حالت یک فراخوانی بازگشتی دیگر داریم.

با دیدن کد جاوای زیر و دقت در خطوط ۳ تا ۱۳ ، منطق راه حل مذکور را در خواهید یافت.

public class CoinChangeRecursion {
    public static int total(int n, int[] v, int i) {
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        // means coins over and n>0 so no solution
        if (i == v.length && n > 0) {
            return 0;
        }
        return total(n - v[i], v, i) + total(n, v, i + 1);
    }

    public static void main(String[] args) {
        int amount = 5;
        int[] v = {
            1,
            2,
            3
        };
        System.out.println("By Recursion: " + total(amount, v, 0));
    }
}

پیچیدگی زمانی راه حل بازگشتی ارائه شده ۲ⁿ است. برای درک این پیچیدگی زمانی، توضیح کوتاهی را در ادامه ارائه می دهیم.

طبق توضیحات ارائه شده، در طی فرآیند بازگشتی این الگوریتم و شمارش حالت های مختلف، هر سکه یا انتخاب می شود یا نمی شود. اگر انتخاب سکه را با ۱ و عدم انتخاب آن را با ۰ نشان دهیم، به طور مثال برای دو سکه حالت های مختلف به شکل ۰۰ ، ۰۱ ، ۱۰ و ۱۱ است که تعداد آن معادل ۲^۲ است. به طریق مشابه برای n سکه ما ۲ⁿ حالت داریم که برای هر کدام هم یک چک ساده انجام می شود. در نهایت برای n سکه زمان اجرای الگوریتم برای پیدا کردن تمام حالت ها از درجه ۲ⁿ خواهد بود.

آیا می توانیم بهتر از این عمل کنیم؟!

اگر کمی به این توضیحات عمیق تر فکر کنید و رشته باینری تمام حالت ها را برای تعداد بیشتری سکه تولید کنید، متوجه می شوید که حالت های تکراری زیادی وجود دارد. این الگوریتم بازگشتی تعداد زیادی زیر مسئله را دوباره و دوباره حل می کند و نتیجه آن همان درجه زمانی بسیار بزرگ است.

با استفاده از برنامه ریزی پویا ما می توانیم الگوریتمی سریع تر و بهینه تر پیاده سازی کنیم.

ب) راه حل تکنیک برنامه ریزی پویا (پایین به بالا)

در این راه حل، ما مقداری حافظه را مشخص می کنیم تا پاسخ بخش هایی از مسئله را که محاسبه شده، نگهداری کنیم؛ و در محاسبه بخش های بعدی (زیرمسئله های بزرگ تر در حل پایین به بالا)، آن ها را استفاده کنیم.

حافظه ای که تعریف و استفاده می کنیم یک ماتریس به نام

solution

[coins+1][amount+1]

حالت های پایه مسئله به شکل زیر است:

• اگر مقدار پول یا amount مساوی سفر باشد، مجموعه جواب ها (مجموعه سکه های انتخاب شده) برابر با مجموعه تهی است که در اینجا یعنی عدم انتخاب هیچ سکه؛ پس به یک شکل می توان پول را خورد کرد.
• اگر تعداد سکه ها مساوی با صفر باشد، به هیچ شکلی نمی توانیم هیچ پولی را خورد کنیم. بنابراین جواب کاملاً تهی است (نه مجموعه تهی).

غیر از موارد بالا، مابقی حالت های مسئله به صورت زیر است:

برای هر سکه ما دو انتخاب داریم، یا از آن سکه برای خورد کردن باقی مانده پول استفاده کنیم یا نکنیم.

اگر برداشتن یک سکه مجاز باشد (یعنی مقدار آن از مقدار باقی مانده پول خورد نشده بزرگ تر نباشد)، آن گاه برداشتن و برنداشتن آن معناهای متفاوتی را ایجاد می کند پس ما مسیرهای متفاوتی را در فراخوانی های بازگشتی برای این حالت ها ایجاد می کنیم.

• برداشتن و استفاده از سکه i ام: مقدار پول باقی مانده (خورد نشده) را به اندازه ارزش سکه کم می کنیم و زیرمسئله (amount-coinValue[i]) را حل می کنیم.
• برنداشتن و عدم استفاده از سکه i ام: زیر مسئله را با همان مقدار باقی مانده و بدون در نظرگرفتن آن سکه (با کمک سکه های بعدی) حل می کنیم.
• اگر استفاده از سکه ای مجاز نباشد (یعنی ارزش آن از باقی مانده پول خورد نشده بزرگ تر باشد)، بدیهی است که در مورد برداشتن آن تصمیم گیری وجود ندارد و به طور قطعی از آن سکه می گذریم.

اگر در زبان ریاضیات بخواهیم مطالب بالا را بیان کنیم، به معادله زیر می رسیم.

معادله حل مسئله خورد کردن پول با روش برنامه ریزی پویای پایین به بالا

به طور مثال برای

Amount = 5
coins [] = {1,2,3}

ماتریس به شکل زیر پر می شود:

ماتریس پر شده برای مثال

بنابراین تمام کاری که ما در این الگوریتم می کنیم، پر کردن یک ماتریس است، که موجب شده زمانی اجرای آن هم از درجه اندازه ماتریس باشد (که بسیار بهینه تر از درجه زمانی حل بازگشتی است).

کد جاوای الگوریتم حل پایین به بالای مسئله در انتهای این مطلب آموزشی از وبسایت اوپن مایند، برای شما عزیزان ارائه شده است.

public class WaysToCoinChange {
    public static int dynamic(int[] v, int amount) {
        int[][] solution = new int[v.length + 1][amount + 1];

        // if amount=0 then just return empty set to make the change
        for (int i = 0; i <= v.length; i++) {
            solution[i][0] = 1;
        }

        // if no coins given, 0 ways to change the amount
        for (int i = 1; i <= amount; i++) {
            solution[0][i] = 0;
        }

        // now fill rest of the matrix.

        for (int i = 1; i <= v.length; i++) {
            for (int j = 1; j <= amount; j++) {
                // check if the coin value is less than the amount needed
                if (v[i - 1] <= j) {
                    // reduce the amount by coin value and
                    // use the subproblem solution (amount-v[i]) and
                    // add the solution from the top to it
                    solution[i][j] = solution[i - 1][j] + solution[i][j - v[i - 1]];
                }
                else {
                    // just copy the value from the top
                    solution[i][j] = solution[i - 1][j];
                }
            }
        }
        return solution[v.length][amount];
    }

    public static void main(String[] args) {
        int amount = 5;
        int[] v = {
            1,
            2,
            3
        };
        System.out.println("By Dynamic Programming " + dynamic(v, amount));
    }

}