Q9.10 To build the tallest stack

2229 ワード

Cracking the coding interview

Q:You have a stack of n boxes, with widths w., heights l\and depths dr The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the heigh t of a stack is the sum of the heights of each box.
A:所与の箱a,b,c,d,e...,では、結果はmax(aをベースとするスタック、bをベースとするスタック、cをベースとするスタック、dをベースとするスタック、eをベースとするスタック...).サブ問題は同様の方法で解き,最下層の判断から逆数第2層の判断に移る.時間を節約するために、メモ方法を採用します.

#include 
#include 
#include 
#include 
using namespace std;

class box {
private:
	float h, w, d;	
public:
	box(float H, float W, float D){
		h = H;
		w = W;
		d =	D;
	}
	bool canBeAbove(box B);
	float getDepth();
};

bool box::canBeAbove(box B){
	if (h vb;
typedef map mvb;

float stackHeight(vb Boxes){
	float height = 0;
	for (int i = 0; i < Boxes.size(); ++i) {
		height += Boxes[i].getDepth();
	}
	return height;
}

vb createStack(mvb &Map, vb Boxes, int bottom) {
	if (Map.count(bottom)!= 0 && bottom < Boxes.size()) {
		return Map[bottom];
	}
	int max_height = 0;
	vb max_stack;
	if (bottom >= Boxes.size()) {
		return max_stack;
	}
	for (int i = 0; i < Boxes.size(); ++i) {
		if (Boxes[i].canBeAbove(Boxes[bottom])) {
			vb tmpStack = createStack(Map, Boxes, i);
			int tmpHeight = stackHeight(tmpStack);
			if (tmpHeight > max_height) {
				max_stack = tmpStack;
				max_height = tmpHeight;
			}
		}
	}
	//Push Boxes[bottom] to font hee
	max_stack.push_back(Boxes[bottom]);
	
	Map[bottom] = max_stack;
	return max_stack;
}

int main(){
	freopen("Question9_10.in", "r", stdin);
	int n;
	cin>>n;
	mvb Map;
	vb Boxes, result;
	float H, W, D;
	for (int i = 0; i < n; ++i) {
		cin>>H>>W>>D;
		cout<

入力データは次のとおりです.

[python]デュアル・ユーティリティ・プリアンブル・キュー

Chromiumソースのコンパイル