C++ fruit greedy algorithm implementation code

C++ fruit greedy algorithm implementation code

(1) title description:

In an orchard, xiaoming has beaten down all the fruits and divided them into piles according to the different kinds of fruits. Xiaoming decides to combine all the fruits into one pile. Every time, xiaoming can combine two piles of fruit into one, and his energy consumption is equal to the weight of the two piles of fruit. Of course, after the merge of n once, it will become a heap. The total energy consumed by xiao Ming in the combination of the fruits is equal to the total energy consumed in each combination.

Assuming that each fruit weighs 1 and that you know the number of types of fruit and the number of each type of fruit, your task is to design a combined sequence so that xiaoming spends the least amount of energy and outputs the minimum amount of energy. For example, there are three kinds of fruit, in order of number 1,2,9. You can merge 1,2 heaps, 3 new heaps, 3 physical exertion. The new heap is then combined with the original third heap to produce the new heap, which consumes 12 energy. Therefore, xiaoming's total energy expenditure is equal to 3+12=15, which can be proved that 15 is the minimum energy expenditure value.

Input:

Each data entry group consists of two lines, the first of which is an integer n(1) < =n < =10000), indicating the number of fruit species. If n = 0, indicating the end of input and no processing. Line 2 contains the n integer, separated by a space, and the i integer (1) < =ai < =1000) is the number of the i fruit.

Output:

For each set of inputs, output 1 integer and line feed, which is the minimum energy cost. The input data is guaranteed to be less than 2^31.

Sample input:

3
9 1 2
0

Sample output:

15

(2) this kind of problem is similar to the Huffman coding, considering that greedy algorithm can be used (combining the smallest pile of fruit at a time). The code is also changed based on the Huffman encoding algorithm. The implementation code is:

PS: the code just implements its functions, not optimizations. Vector is used as a container to store the energy value consumed, and Vector will be traversed once every time Extract_MIN operation is performed. In practice, the efficiency is very low, so the minimum heap structure should be used to store the energy value consumed in practice, which will save a lot of time.

#include <iostream> 
#include <vector> 
 
using namespace std; 
/* 
*  Get the smallest element in the queue  
*/ 
int Extract_MIN(vector<int>& v) 
{ 
  if(v.size() == 0) 
    return -1; 
  int i=0, min_pos = 0; 
  vector<int>::iterator iter = v.begin(); 
  vector<int>::iterator min_iter = v.begin(); 
  for(; iter!=v.end(); ++iter) 
    if((*iter)<(*min_iter)) 
      min_iter = iter; 
  int min_value = *(min_iter); 
  v.erase(min_iter); 
  return min_value; 
} 
/* 
* The calculation process is similar to building a Huffman tree  
*/ 
int MoveFruit(int data[], int n) 
{ 
  // Initialize the element to the queue  
  vector<int> v; 
  int i=0; 
  for(i=0; i<n; ++i) 
    v.push_back(data[i]); 
  int total = 0;// Total energy expenditure  
  // In turn, combination  
  int left = 0, right=0, parent=0;// Every time to merge 1 Heap, select the two smallest Numbers in the queue as the left child and the right child  
  for(i=1; i<n; ++i) 
  { 
     left = Extract_MIN(v); 
     right = Extract_MIN(v); 
     parent = left+right; 
    total += parent; 
    v.push_back(parent); 
  } 
  return total; 
} 
 
int main() 
{ 
  int n; 
  while(cin>>n) 
  { 
    if(n == 0) 
      break; 
    int* data = new int[n]; 
     
    int i=0; 
    for(; i<n; ++i) 
      cin>>data[i]; 
    cout<<MoveFruit(data, n)<<endl; 
        delete[] data; 
    } 
   
} 

Thank you for reading, I hope to help you, thank you for your support of this site!