SHA256
76 lines
2.2 KiB
Markdown
76 lines
2.2 KiB
Markdown
# minimizing-coins
|
|
|
|
## Problem
|
|
### Minimum Number of Coins
|
|
|
|
Consider a money system consisting of `n` coins. Each coin has a positive integer value. Your task is to produce a sum of money `x` using the available coins in such a way that the number of coins is minimized.
|
|
|
|
For example, if the coins are `{1, 5, 7}` and the desired sum is `11`, an optimal solution is `5 + 5 + 1`, which requires 3 coins.
|
|
|
|
---
|
|
|
|
### Input
|
|
|
|
The first input line has two integers `n` and `x`:
|
|
- `n` — the number of coins
|
|
- `x` — the desired sum of money
|
|
|
|
The second line has `n` distinct integers `c₁, c₂, ..., cₙ`: the value of each coin.
|
|
|
|
---
|
|
|
|
### Output
|
|
|
|
Print one integer: the **minimum** number of coins needed to produce the sum `x`.
|
|
If it is **not possible**, print `-1`.
|
|
|
|
---
|
|
|
|
### Constraints
|
|
|
|
- `1 ≤ n ≤ 100`
|
|
- `1 ≤ x ≤ 10⁶`
|
|
- `1 ≤ cᵢ ≤ 10⁶`
|
|
|
|
## Core logic
|
|
|
|
```rust
|
|
fn find_min(cache: &mut HashMap<u64, u64>, target_sum: u64, coins: &Vec<u64>) -> Option<u64> {
|
|
if let Some(&entry) = cache.get(&target_sum) {
|
|
return Some(entry);
|
|
}
|
|
|
|
let mut running_min: u64 = u64::MAX;
|
|
|
|
for &coin in coins {
|
|
if coin > target_sum {
|
|
continue;
|
|
}
|
|
|
|
let new_target = target_sum - coin;
|
|
|
|
if new_target == 0 {
|
|
cache.insert(target_sum, 1); // cache base case
|
|
return Some(1);
|
|
}
|
|
|
|
if let Some(path) = find_min(cache, new_target, coins) {
|
|
let num_coins = 1 + path;
|
|
if num_coins < running_min {
|
|
running_min = num_coins;
|
|
}
|
|
}
|
|
}
|
|
|
|
if running_min != u64::MAX {
|
|
cache.insert(target_sum, running_min);
|
|
Some(running_min)
|
|
} else {
|
|
cache.insert(target_sum, u64::MAX); // Mark as unreachable
|
|
None
|
|
}
|
|
}
|
|
```
|
|
|
|
Essentially, the purpose of the above code is to traverse a tree of possible coin decisions. As long as the coin denomination is smaller than the target, it's possible to recursively iterate through all combinations of coins while both caching and checking for a base case. This behavior is called memorization. The base case for any branch of the tree is when the target sum is equivalent to the coin of interest.
|