C++ 搬水果貪心算法實現代碼。本站提示廣大學習愛好者：（C++ 搬水果貪心算法實現代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是C++ 搬水果貪心算法實現代碼正文

C++ 搬水果貪心算法實現代碼

作者：cscmaker

C++ 搬水果貪心算法實現代碼

（1）題目描述：

    在一個果園裡，小明已經將所有的水果打了下來，並按水果的不同種類分成了若干堆，小明決定把所有的水果合成一堆。每一次合並，小明可以把兩堆水果合並到一起，消耗的體力等於兩堆水果的重量之和。當然經過 n‐1 次合並之後，就變成一堆了。小明在合並水果時總共消耗的體力等於每次合並所耗體力之和。

    假定每個水果重量都為 1，並且已知水果的種類數和每種水果的數目，你的任務是設計出合並的次序方案，使小明耗費的體力最少，並輸出這個最小的體力耗費值。例如有 3 種水果，數目依次為 1，2，9。可以先將 1，2 堆合並，新堆數目為3，耗費體力為 3。然後將新堆與原先的第三堆合並得到新的堆，耗費體力為 12。所以小明總共耗費體力=3+12=15，可以證明 15 為最小的體力耗費值。

輸入：

    每組數據輸入包括兩行,第一行是一個整數 n(1<=n<=10000),表示水果的種類數，如果 n 等於 0 表示輸入結束，且不用處理。第二行包含 n 個整數，用空格分隔，第 i 個整數(1<=ai<=1000)是第 i 種水果的數目。

輸出：

對於每組輸入，輸出一個整數並換行，這個值也就是最小的體力耗費值。輸入數據保證這個值小於 2^31。

樣例輸入：

3
9 1 2
0

樣例輸出：

15

（2）這種問題考慮到可以使用貪心算法（每次都將最小的一堆水果進行合並），問題與赫夫曼編碼類似。代碼也是根據Huffman編碼算法的基礎上的改動，實現代碼為：

     PS：代碼只是實現其功能，沒有優化。使用Vector作為容器，存放耗費的體力值，每執行一次Extract_MIN操作就會遍歷一次Vector，實際當中效率是很低的，所以實際應用當中應該采用 最小堆結構 來存放耗費的體力值，這樣會節省很多時間。

#include <iostream> 
#include <vector> 
 
using namespace std; 
/* 
* 得到隊列中的最小元素 
*/ 
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; 
} 
/* 
*計算過程，類似於構建哈夫曼樹 
*/ 
int MoveFruit(int data[], int n) 
{ 
  //將元素初始化到隊列中 
  vector<int> v; 
  int i=0; 
  for(i=0; i<n; ++i) 
    v.push_back(data[i]); 
  int total = 0;//總體力消耗值 
  //依次組合 
  int left = 0, right=0, parent=0;//每次合並一堆，選取隊列中最小的兩個數作為左孩子和右孩子 
  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; 
    } 
   
} 

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！