Find Minimum Numbers of Currency for Required Amount

Find minimum number of currency notes and values that sum to given amount array issue

To convert float number of notes to integer use Math.trunc or Math.floor: Math.trunc(remaining / note)

The whole code can look like:

function findNoteAndCoins(salary) {
  const notes = [5000, 1000, 500, 100, 50, 20, 10, 5, 2, 1];
  const notesCount = [];

  let remaining = salary;
  for (const note of notes) {
    if (salary >= note) {
      notesCount.push(Math.trunc(remaining / note));
      remaining = remaining % note;
    } else {
      notesCount.push(0);
    }
  }

  return notesCount;
}

console.log(findNoteAndCoins(2316));

and we can check that the findNoteAndCoins function works:

function findSalary(notesCount) {
  const notes = [5000, 1000, 500, 100, 50, 20, 10, 5, 2, 1];
  let salary = 0;
  for (let i = 0; i < notesCount.length; i++) {
    salary += notesCount[i] * notes[i];
  }
  return salary;
}

console.log(findSalary(findNoteAndCoins(2316)) === 2316);

Finding minimum number of notes to make a amount

The error in the algorithm is in the order of two lines that should be the other way around:

least_notes+=n//p 
n=n-(p*n//p) #rest amount of money 

since the least_notes count should be increased before n is updated recursively.

Calculate the Minimum Number of Coins For Given Amount of Change in Haskell

In this answer I will focus on this attempt of yours:

coinChange c [] = []
coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))
                where (x:xs) = (reverse ds)

coinChange' c [] = []
coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )
                where (x:xs) = reverse ds

I think the problem is indeed in the where (x:xs) = reverse ds part in the coinChange' function. Each recursive call reverses the list of denominations. So the xs you get there from the pattern match in that where clause is the reversed list of denominations without the largest denomination. But that list is still reversed, so you shouldn't pass that as an argument to the coinChange or coinChange' functions again. You can reverse this list again before passing it to the recursive call, but that is not very efficient. I would suggest only reversing the denominations in the coinChange function.

Also, the coinChange function can be simplified, because it basically only needs to reverse the denominations and the resulting list.

Here is how that would look:

coinChange c ds = reverse (coinChange' c (reverse ds))

coinChange' c [] = []
coinChange' c (x:xs) = (c `quot` x) : coinChange' (c `rem` x) xs

The minimum number of coins the sum of which is S

This is a classic Knapsack problem, take a look here for some more information: Wikipedia Knapsack Problem

You should also look at some sorting, specifically sorting from Largest to Smallest values.

Denominate the amount with the minimum number of coins with a given face value. Greedy problem

One possible approach is backtracking.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. (Wikipedia)

Here, we try to determine the number of coins, for each coin.

The candidates are abandonned, as soon as the total number of coins is higher than the current optimal solution. Moreover, here, in a given situation (at step i), we directly calculate the maximum number of coins for coins[i], such that the total sum is not higher than the amount.

Here is a possible implementation:

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

std::vector<int> get_change(const std::vector<int>& denominations, int amount) {
    std::vector<int> coins = denominations;
    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 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;
            }
        }
    }

    std::vector<int> ans;

    for (int i = 0; i < coins.size(); i++)
        for (int j = 0; j < n_coins_opt[i]; j++)
            ans.push_back(coins[i]);

    return ans;
}

int main() {
    std::vector<int> coins = { 1, 6, 9 };
    int amount = 30;
    auto n_coins = get_change(coins, amount);

    for (int i = 0; i < n_coins.size(); i++)
            std::cout << n_coins[i] << " ";

    std::cout << "\n";
    return 1;
}

python find the minimum number of coins

Looks like a typo: nickels vs nickles

Edit: now that you've fixed the typo, it looks like it's definitely a rounding issue. Since you're converting from dollars to a whole number of cents, try turning it into an integer before doing any operations.

Change your n1 = n1 * 100 line to n1 = int(round(n1 * 100)). I tried this out on my computer and it seemed to work.

Finding the minimum set of coins that make a given value

I'm assuming you already know the Dynamic Programming method to find only the minimum number of coins needed. Let's say that you want to find the minimum number of coins to create a total value K. Then, your code could be

vector <int> min_coins(K + 1);
min_coins[0] = 0; // base case
for(int k = 1; k <= K; ++k) {
    min_coins[k] = INF;
    for(int c : coins) { // coins[] contains all values of coins
        if(k - c >= 0) {
            min_coins[k] = min(min_coins[k], min_coins[k - c] + 1);
        }
    }
}

Answer to your question: In order to find the actual set of coins that is minimal in size, we can simply keep another array last_coin[] where last_coin[k] is equal to the coin that was last added to the optimal set of coins for a sum of k. To illustrate this:

vector <int> min_coins(K + 1), last_coin(K + 1);
min_coins[0] = 0; // base case
for(int k = 1; k <= K; ++k) {
    min_coins[k] = INF;
    for(int c : coins) {
        if(k - c >= 0) {
            if(min_coins[k - c] + 1 < min_coins[k]) {
                min_coins[k] = min_coins[k - c] + 1;
                last_coin[k] = c; // !!!
            }
        }
    }
}

How does this let you find the set of coins? Let's say we wanted to find the best set of coins that sum to K. Then, we know that last_coin[K] holds one of the coins in the set, so we can add last_coin[K] to the set. After that, we subtract last_coin[K] from K and repeat until K = 0. Clearly, this will construct a (not necessarily the) min-size set of coins that sums to K.

Possible implementation:

int value_left = K;
while(value_left > 0) {
    last_coin[value_left] is added to the set
    value_left -= last_coin[value_left]
}

---

Related Topics