1. Problem Definition
This is a problem to find out which pebbles would be the best choice when trying to take out m pebbles from a given n pebbles.
This problem can be solved using a Greedy Algorithm. The input consists of the weight of each pebble,
and the total weight of the pebbles taken out must not exceed K.
2. Understanding the Problem
Input:
– First line: Number of pebbles n (1 ≤ n ≤ 100)
– Second line: Number of pebbles to take out m (1 ≤ m ≤ n)
– Third line: Weights of n pebbles (1 ≤ weight ≤ 1000)
Output:
– Calculate the total weight of the taken pebbles such that it is maximized to K.
3. Example
Example Input:
5
3
1 2 3 4 5
Example Output:
12 (3 + 4 + 5)
4. Algorithm Design
To solve this problem, first, the weights of the given pebbles need to be sorted, and then the process of selecting the m heaviest pebbles should be performed.
At this point, the total weight of the selected pebbles should be calculated and displayed as the result. The steps of the algorithm are as follows.
- Sort the weights of the pebbles in ascending order.
- Select the last m pebbles from the sorted list.
- Sum the weights of the selected pebbles and display the result.
5. Code Implementation
Now, let’s implement the C++ code based on the above algorithm.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, m;
std::cout << "Please enter the number of pebbles: ";
std::cin >> n;
std::cout << "Please enter the number of pebbles to take out: ";
std::cin >> m;
std::vector<int> weights(n);
std::cout << "Please enter the weights of the pebbles (separated by spaces): ";
for (int i = 0; i < n; ++i) {
std::cin >> weights[i];
}
// Sort the weights of the pebbles
std::sort(weights.begin(), weights.end());
// Select the heaviest m pebbles
int total_weight = 0;
for (int i = n - m; i < n; ++i) {
total_weight += weights[i];
}
std::cout << "Total weight of selected pebbles: " << total_weight << std::endl;
return 0;
}
6. Code Explanation
The above C++ code takes input for the number of pebbles and the number of pebbles to be selected, and stores the weights of each pebble in an array.
Then, it uses the STL sort function to sort the weights. It selects the heaviest m pebbles from the sorted array to calculate and display the total weight.
7. Algorithm Complexity Analysis
The time complexity of this algorithm is O(n log n), where n is the number of pebbles. The sorting process takes the largest share of the computation time.
The space complexity is O(n), which is the memory needed to store the weights of the input pebbles.
8. Problem Solving Reflection
This problem is a good practice problem for learning the basics of greedy algorithms. Through the pebble selection problem,
one can learn methods for making optimized choices. Similar problems frequently appear in actual coding tests, so
repetitive practice is necessary. I hope you gain more experience by solving various problems in the future.