در این مطلب، هدف محاسبه حداقل تعداد سکه لازم برای یک مقدار مشخص است. به عبارت دیگر، مقدار V داده شده است. اگر کاربر بخواهد مقدار V را با کمترین تعداد سکه بسازد و تعداد محدودی از هر سکه داشته باشد، چطور باید این کار را انجام دهد. فرض می‌شود C = { C1, C2, .. , Cm}‎ مقدار سکه‌ها هستند.

مثال:

Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents 

Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents

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

If V == 0, then 0 coins required.
If V > 0
minCoins(coins[0..m-1], V) = min {1 + minCoins(V-coin[i])}
where i varies from 0 to m-1
and coin[i] <= V

در ادامه، کد مربوط به پیاده‌سازی راهکار بازگشتی بالا، ارائه شده است.

پیاده‌سازی در ++C

// A Naive recursive C++ program to find minimum of coins 
// to make a given change V 
#include<bits/stdc++.h> 
using namespace std; 
  
// m is size of coins array (number of different coins) 
int minCoins(int coins[], int m, int V) 
{ 
   // base case 
   if (V == 0) return 0; 
  
   // Initialize result 
   int res = INT_MAX; 
  
   // Try every coin that has smaller value than V 
   for (int i=0; i<m; i++) 
   { 
     if (coins[i] <= V) 
     { 
         int sub_res = minCoins(coins, m, V-coins[i]); 
  
         // Check for INT_MAX to avoid overflow and see if 
         // result can minimized 
         if (sub_res != INT_MAX && sub_res + 1 < res) 
            res = sub_res + 1; 
     } 
   } 
   return res; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int coins[] =  {9, 6, 5, 1}; 
    int m = sizeof(coins)/sizeof(coins[0]); 
    int V = 11; 
    cout << "Minimum coins required is "
         << minCoins(coins, m, V); 
    return 0; 
}

پیاده‌سازی در جاوا

// A Naive recursive JAVA program to find minimum of coins 
// to make a given change V 
class coin 
{ 
    // m is size of coins array (number of different coins) 
    static int minCoins(int coins[], int m, int V) 
    { 
       // base case 
       if (V == 0) return 0; 
       
       // Initialize result 
       int res = Integer.MAX_VALUE; 
       
       // Try every coin that has smaller value than V 
       for (int i=0; i<m; i++) 
       { 
         if (coins[i] <= V) 
         { 
             int sub_res = minCoins(coins, m, V-coins[i]); 
       
             // Check for INT_MAX to avoid overflow and see if 
             // result can minimized 
             if (sub_res != Integer.MAX_VALUE && sub_res + 1 < res) 
                res = sub_res + 1; 
         } 
       } 
       return res; 
    } 
    public static void main(String args[]) 
    { 
       int coins[] =  {9, 6, 5, 1}; 
       int m = coins.length; 
       int V = 11; 
       System.out.println("Minimum coins required is "+ minCoins(coins, m, V) ); 
    } 
}/* This code is contributed by Rajat Mishra */

پیاده‌سازی در پایتون ۳

# A Naive recursive python program to find minimum of coins 
# to make a given change V 
  
import sys 
  
# m is size of coins array (number of different coins) 
def minCoins(coins, m, V): 
  
    # base case 
    if (V == 0): 
        return 0
  
    # Initialize result 
    res = sys.maxsize 
      
    # Try every coin that has smaller value than V 
    for i in range(0, m): 
        if (coins[i] <= V): 
            sub_res = minCoins(coins, m, V-coins[i]) 
  
            # Check for INT_MAX to avoid overflow and see if 
            # result can minimized 
            if (sub_res != sys.maxsize and sub_res + 1 < res): 
                res = sub_res + 1
  
    return res 
  
# Driver program to test above function 
coins = [9, 6, 5, 1] 
m = len(coins) 
V = 11
print("Minimum coins required is",minCoins(coins, m, V)) 
  
# This code is contributed by 
# Smitha Dinesh Semwal

پیاده‌سازی در #C

// A Naive recursive C# program 
// to find minimum of coins 
// to make a given change V 
using System; 
class coin 
{ 
      
    // m is size of coins array  
    // (number of different coins) 
    static int minCoins(int []coins, int m, int V) 
    { 
          
        // base case 
        if (V == 0) return 0; 
          
        // Initialize result 
        int res = int.MaxValue; 
          
        // Try every coin that has 
        // smaller value than V 
        for (int i = 0; i < m; i++) 
        { 
            if (coins[i] <= V) 
            { 
                int sub_res = minCoins(coins, m, 
                                  V - coins[i]); 
          
                // Check for INT_MAX to  
                // avoid overflow and see  
                // if result can minimized 
                if (sub_res != int.MaxValue &&  
                            sub_res + 1 < res) 
                    res = sub_res + 1; 
            } 
        } 
        return res; 
    } 
      
    // Driver Code 
    public static void Main() 
    { 
        int []coins = {9, 6, 5, 1}; 
        int m = coins.Length; 
        int V = 11; 
        Console.Write("Minimum coins required is "+ 
                             minCoins(coins, m, V)); 
    } 
} 
  
// This code is contributed by nitin mittal.

پیاده‌سازی در PHP

<?php 
// A Naive recursive PHP  
// program to find minimum  
// of coins to make a given 
// change V 
  
// m is size of coins array  
// (number of different coins) 
function minCoins($coins,  
                  $m, $V) 
{ 
      
// base case 
if ($V == 0) return 0; 
  
// Initialize result 
$res = PHP_INT_MAX; 
  
// Try every coin that has 
// smaller value than V 
for ($i = 0; $i < $m; $i++) 
{ 
    if ($coins[$i] <= $V) 
    { 
        $sub_res = minCoins($coins, $m, 
                            $V - $coins[$i]); 
  
        // Check for INT_MAX to  
        // avoid overflow and see 
        // if result can minimized 
        if ($sub_res != PHP_INT_MAX &&  
            $sub_res + 1 < $res) 
            $res = $sub_res + 1; 
    } 
} 
return $res; 
} 
  
// Driver Code 
$coins = array(9, 6, 5, 1); 
$m = sizeof($coins); 
$V = 11; 
echo "Minimum coins required is ", 
         minCoins($coins, $m, $V); 
      
// This code is contributed by ajit 
?>

خروجی قطعه کدهای بالا، در ادامه آمده است.

Minimum coins required is 2

پیچیدگی زمانی راهکار بالا به صورت نمایی است. اگر یک درخت بازگشتی کامل ترسیم شود، می‌توان مشاهده کرد که بسیاری از زیر مسائل، چندین بار حل می‌شوند. برای مثال، کار از V = 11 آغاز می‌شود. می‌توان با پنج بار تفریق کردن یک یا یک بار تفریق کردن پنج، به ۶ رسید. از آنجا که زیرمسائل مشابهی فراخوانی می‌شوند، این مساله دارای خصوصیت مسائل دارای هم‌پوشانی است. بنابراین، مساله حداقل سکه‌ها دارای هر دو خصوصیت «برنامه‌نویسی پویا» (Dynamic Programming) است. همچون دیگر انواع مسائل برنامه‌نویسی پویا، محاسبه مجدد زیر مسائل مشابه با ساخت یک جدول آرایه موقتی [][] به صورت پایین به بالا، قابل حل است. در ادامه، راهکار مبتنی بر برنامه‌نویسی خطی ارائه شده است.

حل مساله حداقل تعداد سکه‌ها با برنامه‌نویسی پویا در C++‎

// A Dynamic Programming based C++ program to find minimum of coins 
// to make a given change V 
#include<bits/stdc++.h> 
using namespace std; 
  
// m is size of coins array (number of different coins) 
int minCoins(int coins[], int m, int V) 
{ 
    // table[i] will be storing the minimum number of coins 
    // required for i value.  So table[V] will have result 
    int table[V+1]; 
  
    // Base case (If given value V is 0) 
    table[0] = 0; 
  
    // Initialize all table values as Infinite 
    for (int i=1; i<=V; i++) 
        table[i] = INT_MAX; 
  
    // Compute minimum coins required for all 
    // values from 1 to V 
    for (int i=1; i<=V; i++) 
    { 
        // Go through all coins smaller than i 
        for (int j=0; j<m; j++) 
          if (coins[j] <= i) 
          { 
              int sub_res = table[i-coins[j]]; 
              if (sub_res != INT_MAX && sub_res + 1 < table[i]) 
                  table[i] = sub_res + 1; 
          } 
    } 
    return table[V]; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int coins[] =  {9, 6, 5, 1}; 
    int m = sizeof(coins)/sizeof(coins[0]); 
    int V = 11; 
    cout << "Minimum coins required is "
         << minCoins(coins, m, V); 
    return 0; 
}

حل مساله حداقل تعداد سکه‌ها با برنامه‌نویسی پویا در جاوا

// A Dynamic Programming based Java 
// program to find minimum of coins 
// to make a given change V 
import java.io.*; 
  
class GFG  
{ 
    // m is size of coins array  
    // (number of different coins) 
    static int minCoins(int coins[], int m, int V) 
    { 
        // table[i] will be storing  
        // the minimum number of coins 
        // required for i value. So  
        // table[V] will have result 
        int table[] = new int[V + 1]; 
  
        // Base case (If given value V is 0) 
        table[0] = 0; 
  
        // Initialize all table values as Infinite 
        for (int i = 1; i <= V; i++) 
        table[i] = Integer.MAX_VALUE; 
  
        // Compute minimum coins required for all 
        // values from 1 to V 
        for (int i = 1; i <= V; i++) 
        { 
            // Go through all coins smaller than i 
            for (int j = 0; j < m; j++) 
            if (coins[j] <= i) 
            { 
                int sub_res = table[i - coins[j]]; 
                if (sub_res != Integer.MAX_VALUE  
                       && sub_res + 1 < table[i]) 
                       table[i] = sub_res + 1; 
                         
                  
            } 
              
        } 
        return table[V]; 
          
    } 
  
    // Driver program  
    public static void main (String[] args)  
    { 
        int coins[] = {9, 6, 5, 1}; 
        int m = coins.length; 
        int V = 11; 
        System.out.println ( "Minimum coins required is " 
                            + minCoins(coins, m, V)); 
    } 
} 
  
//This Code is contributed by vt_m.

حل مساله حداقل تعداد سکه‌ها با برنامه‌نویسی پویا در پایتون ۳

# A Dynamic Programming based Python3 program to  
# find minimum of coins to make a given change V 
import sys  
  
# m is size of coins array (number of  
# different coins) 
def minCoins(coins, m, V): 
      
    # table[i] will be storing the minimum  
    # number of coins required for i value.  
    # So table[V] will have result 
    table = [0 for i in range(V + 1)] 
  
    # Base case (If given value V is 0) 
    table[0] = 0
  
    # Initialize all table values as Infinite 
    for i in range(1, V + 1): 
        table[i] = sys.maxsize 
  
    # Compute minimum coins required  
    # for all values from 1 to V 
    for i in range(1, V + 1): 
          
        # Go through all coins smaller than i 
        for j in range(m): 
            if (coins[j] <= i): 
                sub_res = table[i - coins[j]] 
                if (sub_res != sys.maxsize and 
                    sub_res + 1 < table[i]): 
                    table[i] = sub_res + 1
    return table[V] 
  
# Driver Code 
if __name__ == "__main__": 
  
    coins = [9, 6, 5, 1] 
    m = len(coins) 
    V = 11
    print("Minimum coins required is ",  
                 minCoins(coins, m, V)) 
  
# This code is contributed by ita_c

حل مساله حداقل تعداد سکه‌ها با برنامه‌نویسی پویا در C#‎

// A Dynamic Programming based  
// Java program to find minimum  
// of coins to make a given  
// change V 
using System; 
  
class GFG 
{ 
  
// m is size of coins array  
// (number of different coins) 
static int minCoins(int []coins, 
                    int m, int V) 
{ 
    // table[i] will be storing  
    // the minimum number of coins 
    // required for i value. So  
    // table[V] will have result 
    int []table = new int[V + 1]; 
  
    // Base case (If given 
    // value V is 0) 
    table[0] = 0; 
  
    // Initialize all table 
    // values as Infinite 
    for (int i = 1; i <= V; i++) 
    table[i] = int.MaxValue; 
      
    // Compute minimum coins  
    // required for all 
    // values from 1 to V 
    for (int i = 1; i <= V; i++) 
    { 
        // Go through all coins 
        // smaller than i 
        for (int j = 0; j < m; j++) 
        if (coins[j] <= i) 
        { 
            int sub_res = table[i - coins[j]]; 
            if (sub_res != int.MaxValue &&  
                sub_res + 1 < table[i]) 
                table[i] = sub_res + 1; 
        } 
    } 
    return table[V]; 
      
} 
  
// Driver Code  
static public void Main () 
{ 
    int []coins = {9, 6, 5, 1}; 
    int m = coins.Length; 
    int V = 11; 
    Console.WriteLine("Minimum coins required is " +  
                             minCoins(coins, m, V)); 
} 
} 
  
// This code is contributed  
// by akt_mit

حل مساله حداقل تعداد سکه‌ها با برنامه‌نویسی پویا در PHP

<?php 
// A Dynamic Programming based  
// PHP program to find minimum  
// of coins to make a given  
// change V. 
  
// m is size of coins  
// array (number of different coins) 
function minCoins($coins, $m, $V) 
{ 
    // table[i] will be storing the 
    // minimum number of coins 
    // required for i value. So  
    // table[V] will have result 
    $table[$V + 1] = array(); 
  
    // Base case (If given 
    // value V is 0) 
    $table[0] = 0; 
  
    // Initialize all table  
    // values as Infinite 
    for ($i = 1; $i <= $V; $i++) 
        $table[$i] = PHP_INT_MAX; 
  
    // Compute minimum coins  
    // required for all 
    // values from 1 to V 
    for ($i = 1; $i <= $V; $i++) 
    { 
        // Go through all coins 
        // smaller than i 
        for ($j = 0; $j < $m; $j++) 
        if ($coins[$j] <= $i) 
        { 
            $sub_res = $table[$i - $coins[$j]]; 
            if ($sub_res != PHP_INT_MAX &&  
                $sub_res + 1 < $table[$i]) 
                $table[$i] = $sub_res + 1; 
        } 
    } 
    return $table[$V]; 
} 
  
// Driver Code 
$coins = array(9, 6, 5, 1); 
$m = sizeof($coins); 
$V = 11; 
echo "Minimum coins required is ", 
    minCoins($coins, $m, $V); 
  
// This code is contributed by ajit 
?>

خروجی قطعه کدهای بالا، به صورت زیر است.

Minimum coins required is 2

پیچیدگی زمانی روش بالا از درجه O(mV)‎ است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
• برنامه تشخیص وجود دور در گراف جهت‌دار — راهنمای کاربردی
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده

منبع [+]