贏者樹

Winn Winn 贏者。

1．基本東西：
形象來說，外部節點表示選手捉對廝殺，內部節點表示比賽的勝者（敗者）。定
義如下：對於n名選手，贏者樹是一棵含n個外部節點，n-1個內部節點的完全二叉樹
，其中每個內部節點記錄了相應賽局的贏家（或輸家）。
贏者樹的一個優點在於即使一名選手得分改變了，也只需修改從它到根的那條路徑
，而不必改變其他比賽結果。
2．抽象數據描述-WinnerTree
WinnerTree{
實例：
完全二叉樹，每個節點表示相應比賽的贏者，外部節點表示選手；
操作：
creat()---創建一個空的贏者樹；
Initialize(a,n)：對有n個選手a[1:n]的贏者樹進行初始化；
Winner()---返回比賽的贏者；
Replay(i)---選手i變化時，重組贏者樹；
}；
3．類WinnerTree （202.38.64.10/~wurong/Ctree.rar）
n名選手的贏者樹需要n-1個內部節點t[1:n-1]。選手（外部節點）用e[1:n]表示
。故t為數組e的一個索引而且類型為int。t給出了贏者樹中節點i對應比賽的
贏者。為了實現ADT操作，必須能夠確定外部節點e的父節點t[p]。根據贏者樹完
全二叉樹的特點，最低層最左端的內部節點編號為2S,這裡s=log2(n-1)因此最低層
內部節點數目為n-2S，那么相應的最低層的外部節點數目LowExt應該為這個數值的
2倍，那么倒數第二層的最左端外部節點號為LowExt+1，設offset=2S+1-1，可知對
於任何外部節點e，其父節點t[p]滿足一下關係：
p== (i+offset)/2 i<=LowExt
(i-LowExt+n-1)/2 i>LowExt
類定義：私有成員包括：MaxSize(允許最大選手數),n(贏者樹初始化時選手數)
,t(內部節點數組),e(外部節點數組),LowExt和Offset。通過適當定義Winner，可以
構造最小贏者樹，最大贏者樹等。初始化和replay函式是通過比賽來進行的。
4．輸者樹
對於函式RePlay(i)函式，採用輸者樹效率比贏者樹高，但是也僅限於這個情況
而已。
5．套用
①最先匹配法求解箱子裝載問題：
問題描述：若干個容量為c的箱子和n個待裝入箱子的物品，物品i需要占用s
個單元，所謂成功裝載是把所有物品裝入箱子而不溢出，而最優裝載則是指使用了
最少箱子的成功裝載。
對於此類箱子問題，流行4種算法：
A．最先匹配法（FF）：物品按照1,2,…,n的順序裝入箱子，假設箱子從左向右
排列，每一物品i放入可盛載它的最左箱子。
B．最優匹配法（BF）：設cAvail[j]為箱子j的可用容量，出示時所有都為c，物
品i放入具有最小cAvail且容量大於s的箱子中
C．最先匹配遞減法（FFD）：與FF類似，區別在於各物品首先按照容量遞減的次
序排列。
D．最優匹配遞減法（bfd）：於BF類似，區別在於各物品首先按照容量遞減的次序
排列。
這裡設計最先匹配程式。程式首先要求輸入物品數量n及每個箱子的容量c。假定容
量及空間需求均為整數，接下來程式要求輸入n個物品並限制每個物品孔間<=c。最
後再調用函式FirstFitBack，將物品分派到各個箱子。對於使用FFD策略的程式，只
需將源程式稍作修改，即在調用FirstFitBack前按遞減順序對物品進行排序。
對於FirstFitBack函式，選手i代表箱子i當前的容量，所有箱子容量初始化為c。該
函式假定，當比賽開始時左邊選手是贏者，除非右邊選手比較大。
具體代碼見firstfit.cpp
②用相鄰匹配法求解箱子裝載問題：
Next Fit策略中，開始將物品1放入箱子1，對於其餘物品，則從最後使用的箱子的
下一個箱子開始。比如箱子1~b正在使用，則可認為這些箱子排列成環狀：i!=b時，
i的下一個箱子為i+1；i=b時，i的下一個箱子為箱子1。若上一個物品放入了箱子j
，則從箱子j的下一個箱子開始不斷查找後續箱子，直到找到具有足夠空間的箱子或
者又回到箱子j。若沒有找到合適的，則啟用一新箱子。