Sponsored
Sponsored
This approach uses dynamic programming to find the maximum value of k coins from the given piles. We maintain a DP table where dp[i][j] represents the maximum value of coins we can obtain using the first i piles and j picks.
The main idea is to update this table by considering the top coin from the current pile, and deciding whether or not to pick it. We also keep track of cumulative sums for quicker reference.
Time Complexity: O(n * k * m), where n is the number of piles, k is the number of coins to pick, and m is the average number of coins in each pile.
Space Complexity: O(n * k)
1function maxValueOfCoins(piles, k) {
2 const n = piles.length;
3 const dp = Array(n + 1).fill(0).map(() => Array(k + 1).fill(0));
4
5 for (let i = 1; i <= n; i++) {
6 const currentPile = piles[i - 1];
7 let pileSum = 0;
8
9 for (let j = 0; j < currentPile.length; j++) {
10 pileSum += currentPile[j];
11 for (let x = k; x >= j + 1; x--) {
12 dp[i][x] = Math.max(dp[i][x], dp[i - 1][x - (j + 1)] + pileSum);
13 }
14 }
15 }
16
17 return dp[n][k];
18}
19
20// Example usage:
21// const piles = [[1, 100, 3], [7, 8, 9]];
22// const k = 2;
23// console.log(maxValueOfCoins(piles, k)); // Output: 101The JavaScript solution creates a two-dimensional array dp and iteratively updates it with the maximum coin values. Cumulative sums of coins are used to efficiently maximize the values as we loop through piles and allowed coins.
This approach involves greedy selection to achieve a near-optimal solution. The idea is to always select the coin with the highest value from a potential list of top coins from each pile, and repeat this k times.
This method might not guarantee the absolute optimal solution due to local-optimal greediness but can offer a reasonable approximation for certain constraints and datasets.
Time Complexity: O(k log n), as we perform k heap operations on n piles.
Space Complexity: O(n), due to storing piles in the heap.
1#include <vector>
2#include <queue>
3using namespace std;
4
int maxValueOfCoins(vector<vector<int>>& piles, int k) {
struct Compare {
bool operator()(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
};
priority_queue<vector<int>, vector<vector<int>>, Compare> max_heap;
for (auto& pile : piles) {
max_heap.push({pile[0], 0, (int)pile.size(), (int)&pile - (int)&piles[0]});
}
int total_value = 0;
for (int _ = 0; _ < k; ++_) {
auto top = max_heap.top();
max_heap.pop();
int value = top[0], index = top[1], size = top[2];
int pile_idx = top[3];
total_value += value;
if (index + 1 < size) {
int next_value = piles[pile_idx][index + 1];
max_heap.push({next_value, index + 1, size, pile_idx});
}
}
return total_value;
}
// Example usage:
// vector<vector<int>> piles = {{1, 100, 3}, {7, 8, 9}};
// int k = 2;
// int result = maxValueOfCoins(piles, k); // Output: 101The C++ solution makes use of a priority queue to simulate a max-heap, ensuring that the highest value coins are picked. It efficiently tracks the index in each pile for successive selections.