C++ 找零问题程序

在本文中，我们将看到最常见的面试问题。找零问题是动态规划方法的一个很好的示例。现在让我们理解问题陈述。

问题陈述

给定N和一个包含一些数字（代表硬币面值）的数组(coins[])。N是需要找零的金额，数组包含各种面值的硬币。任务是使用数组中的硬币进行找零。找零的方式是使用尽量少的硬币。

示例

让我们以一个输入数组coins[] = {10, 25, 5}，硬币总数为3为例。

我们有N = 30。

输出结果是 two ，因为我们可以使用一个25卢比的硬币和一个5卢比的硬币组成30（25 + 5 = 30）。

同样，coins[] = {1, 9, 6, 5}，硬币总数为4。

N = 13。

输出结果是 three ，因为我们需要两个6卢比的硬币和一个1卢比的硬币（6 + 6 + 1 = 13）。

方法1

该方法使用递归方法。我们从N开始，每次迭代时，将问题分解为较小的子问题。这是通过从硬币数组中取出每个硬币并从N中减去来完成的。当N等于零时，我们得到了所需的解决方案。为了得到最优的答案，我们返回所有组合中的最小值。

C++代码

#include 
using namespace std;


int minCoins(int coins[], int total_coins, int N) // Function to return the minimum // coins needed 
{
        if (N == 0) // If we have a combination then 
        return 0;

    int result = INT_MAX; // Currently result is initialised as INT_MAX 

    for (int i = 0; i < total_coins; i++) // run until availability of coins
    {
        if (coins[i] <= N) { // Add to the list of counting 
            int sub_res = 1 + minCoins(coins, total_coins, N - coins[i]); // add 1 due to the coin inclusion
            // see if result can minimize
            if (sub_res < result)
                result = sub_res;
        }
    }
    return result;
}

int main()
{
    int coins[] = { 10, 25, 5 };
    int sum = 30; // the money to convert
    int total_coins = 3; // total availability of coins
    cout << "Minmum coins needed are " << minCoins(coins, total_coins, sum);
}

输出

Minimum coins needed are 2

上述解决方案对于更大的输入不起作用。在这种情况下，递归的方法会失败。

现在让我们来看一种优化的方法。

方法2

这种方法使用自底向上的动态规划思想。

由于子问题反复计算，存在重叠子问题的条件。可以使用记忆化的属性解决重复计算的问题，即创建一个dp[]数组，用于存储特定阶段的计算值。在每个阶段计算所有可能的组合。在所有组合之后，dp[]数组的最后一个值给出了答案。

C++代码

#include <bits/stdc++.h>
using namespace std;

int coins[] = { 10, 25, 5 }; // coins array
int dp[1000] = { 0 }; // array for memoisation
int minCoins(int N, int M) // N is the sum , M is total_coins
{

    for (int i = 0; i <= N; i++)
        dp[i] = INT_MAX; // Initialise all dp[] value to INT_MAX

    dp[0] = 0; // Base case if sum becomes zero min rupees = 0

    //Iterating in the outer loop for possible values of sum between 1 to N
    //Since our final solution for sum = N might depend upon any of these values
    for (int i = 1; i <= N; i++) {
        //Inner loop denotes the index of coin array.
        //For each value of sum, to obtain the optimal solution.
        for (int j = 0; j < M; j++) {
            //i ?> sum
            //j ?> next coin index
            //If we can include this coin in our solution
            if (coins[j] <= i) {
                //Solution might include the newly included coin
                dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
            }
        }
    }
    return dp[N];
}

int main()
{

    int sum = 30; // the money to convert
    int total_coins = 3; // total availability of coins
    cout << "Minimum coins needed are " << minCoins(sum, total_coins);
}

输出