14.6 問題 5 瓶詰め問題解いた

読み終わったけど,今朝やってみたら意外と解けたので書いておく.
ヒープは簡単に実装できる割に凄い.でもプライオリティキューとか聞くとどうしても,
スケジューラ->形式検証必須(平等とか)->手が出せないorz みたいな印象が…なぜだろう？

問題

それぞれ0から1までの間の大きさ(ウエイト)を持ったn個の要素があったとし、
それを容量が1のビンに詰めていくとする。
このとき、なるべくビンの数を少なくするにはどうしたらよいか…

解法

ビンの空き容量で順序づけた要素をヒープに入れ,
出来る限り左(下)のビンに詰めていく.空いてなければ右に.左右とも空いてなければその親要素に詰める.
…というかんじで実装した.(ファーストフィット法と云うらしい)

// 使い方
int main(){
	int N=100;
	FstFit h(N);

	for(int i=0; i<N; i++){
		h.insert(0);	// 何も入ってない状態のビンをN個登録
	}
	for(int i=0; i<N; i++){
		int x=N*(double)rand()/RAND_MAX;
		h.pack(x);	// 詰めます. 超詰めます.
	}
	h.print();
}

実装

ヒープクラス概要

class Heap {
protected:
	int * xs_;	// データ(xs_+1以降しか使用しない)
	int len;	// 保持出来るデータ数
	int size_;	// 保持しているデータ数
	void shiftup(int N);
	void shiftdown(int N);
public:
	Heap(int N) : xs_(new int[N+1]), len(N+1), size_(0) {}

	// 良きにはからへ
	void print(void) const;
	int get_size() const { return size_; }
	void insert(int v);
	int get_min(void);

	~Heap()
	{ delete xs_; }
};

実際にびんずめする部分

class FstFit : public Heap {
	int weight_; // ビンの容量
public:

	FstFit(int N) : Heap(N), weight_(N) {}
	void pack(int w);
};

void FstFit::pack(int w){
	int N=1;
	while(N<size_/2){
		int left=N*2;
		int right=N*2+1;

		if(xs_[left]+w<=weight_){		// 左に詰められる
			N=left;
		}else{
			if(xs_[right]+w<=weight_){	// 右に詰められる
				N=right;
			}else{
				break;			// どっちもいっぱい＼(^o^)／
			}
		}
	}

	xs_[N]+=w;	// ウエイトを足し込んで,
	shiftdown(N);	// ヒープを再構築
}