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
Postman: How to Check Whether the Field Is Returning Null in the Postman Automation
Pass Dynamic Object in Onclick - Javascript/Jquery
How to Add Node Module to Angular Project If Is Not Schematics Enabled
Changing the Value of Json Object's Key, Changes Other Values Also
How to Clear Input After Onclick With Reactjs
Dynamically Increase and Decrease an Input Text Box Size Depending on Another Selector Width
How to Play Audio File into Channel
How to Convert Gmt Time to Ist Time in JavaScript
How to Convert Raw Mp3 Binary into Blob Url and Play It in Audio Tag
Keep Selected Dropdown Result After Refreshing Page, Jquery
How to Bind on Click Event on Dynamically Created Button in Angular 6
React Jsx - Make Substring in Bold
Detect If a Field Is Updated With JavaScript or Jquery
How to Clear Browsing History Using JavaScript
Accessing Variables from Other Functions Without Using Global Variables
How to Extract Data from Json Nested Objects