Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement Dynamic Programming Approach for Change Calculation #6

Open
5 tasks
samjowen opened this issue Mar 16, 2023 · 0 comments
Open
5 tasks

Implement Dynamic Programming Approach for Change Calculation #6

samjowen opened this issue Mar 16, 2023 · 0 comments
Labels
algorithms enhancement New feature or request

Comments

@samjowen
Copy link
Owner

Currently, our crate uses a greedy algorithm for calculating the optimal change for various currencies. While this approach works well for many currencies, it might not provide the optimal solution for custom currencies with specific denominations.

We want to implement the dynamic programming approach as an alternative to the greedy algorithm. This will ensure that we can provide the most accurate change calculation for custom currencies and any other currencies where the greedy approach fails to give the optimal solution.

To accomplish this task, we need to:

  • Implement the dynamic programming algorithm for change calculation.
  • Update the CurrencyKind enum to include a method for specifying the recommended algorithm (greedy or dynamic) for each currency.
  • Update the change calculation function to use the recommended algorithm based on the input currency.
  • Add tests to verify the correctness of the dynamic programming approach.
  • Update the README to explain the two algorithms and how the crate chooses the best one for each currency.

By implementing the dynamic programming approach, we can improve the versatility and accuracy of our crate, making it more appealing to potential users and contributors.

@samjowen samjowen added enhancement New feature or request algorithms labels Mar 16, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
algorithms enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant