Find the optimal coin set | Yaozong's Blog
You are given an integer N and an integer M. You are supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),…, 6 = 1 + 5 (2 coins), …, 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 (8 coins), and we take the average of these coins, we would see that the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.
Read full article from Find the optimal coin set | Yaozong's Blog
You are given an integer N and an integer M. You are supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),…, 6 = 1 + 5 (2 coins), …, 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 (8 coins), and we take the average of these coins, we would see that the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.
pair<vector<int>, double> find_optimal_set(int M, int N)
{
vector<vector<int>> all_subsets;
vector<int> cur;
find_subsets(2, M, N - 1, cur, all_subsets);
for (int i = 0; i < all_subsets.size(); ++i)
all_subsets[i].insert(all_subsets[i].begin(), 1);
double min_cost = DBL_MAX;
vector<int> sol;
for (int i = 0; i < all_subsets.size(); ++i)
{
double cost = compute_average(all_subsets[i], M);
if (cost < min_cost) {
min_cost = cost;
sol = all_subsets[i];
}
}
return{ sol, min_cost };
}
double compute_average(vector<int>& coins, int M)
{
int res = 0;
vector<int> cache(M + 1, -1);
cache[0] = 0;
for (int i = 1; i <= M; ++i)
res += minimum_coins(coins, i, cache);
return res * 1.0 / M;
}
void find_subsets(int start, int end, int N, vector<int>& cur, vector<vector<int>>& res)
{
if (start > end) {
if (N == 0)
res.push_back(cur);
return;
}
if (N == 0) {
res.push_back(cur);
return;
}
cur.push_back(start);
find_subsets(start + 1, end, N - 1, cur, res);
cur.pop_back();
find_subsets(start + 1, end, N, cur, res);
}
int minimum_coins(vector<int>& coins, int target, vector<int>& cache)
{
if (cache[target] >= 0)
return cache[target];
int res = INT_MAX;
for (int i = 0; i < coins.size(); ++i) {
if (target >= coins[i])
res = min(res, 1 + minimum_coins(coins, target - coins[i], cache));
}
cache[target] = res;
return res;
}
};
https://www.quora.com/How-do-I-find-the-optimal-coins-to-carry-that-covers-all-the-change-in-the-range-of-1-to-CRead full article from Find the optimal coin set | Yaozong's Blog
