算法分析作业-钻石金字塔问题

有一座金字塔，金字塔的每块石头上都镶有对应的钻石，，不同的钻石有着不同的价值。现在从金字塔的顶端向金字塔的底端收集钻石，并且尽可能收集价值高的钻石，但是只能从一块砖斜向左下或斜向右下走到另一块砖上找到一个收集最高价值钻石的路线，并且告知可能收集的最大价值。 压缩包中含有代码.cpp，文档，可执行文件exe

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

typedef struct brick {
	int key;		//该位置砖石的价值
	int seleted;	//是否被更上一级选择
	int sum;		//从该点向下的最大价值
}brick;

void Output_ini（int N brick**a）		//输出最初的金字塔
{
	for （int i =0; i <= N-1; i++） {
		for （int j = 0; j <= i; j++） {
			if （j == 0） {
				for （int k = 0; k < N - i - 1; k++）
					cout << setw（4） << “ “;		//用setw设置输出宽度
			}
			cout << setw（4） << a[i][j].key;
			cout << setw（4） << “ “;
		}
		cout << endl;
	}
	cout << endl;
}
void clear（int N brick**a）		//将无用的selected置为零
{
	for （int i = 1; i <= N - 1; i++） {
		for （int j = 0; j <= i; j++） {
			if （j == 0 && a[i - 1][j].seleted == 0）
				a[i][j].seleted = 0;
			else if （j == i && a[i - 1][j - 1].seleted == 0）
				a[i][j].seleted = 0;
			else if （j != 0 && j != i && a[i - 1][j].seleted == 0 && a[i - 1][j - 1].seleted == 0）
				a[i][j].seleted = 0;
			else if （j != 0 && j != i && a[i - 1][j].seleted == 0 && a[i - 1][j - 1].seleted != 0 &&
				a[i][j].sum != a[i - 1][j - 1].sum - a[i - 1][j - 1].key）
				a[i][j].seleted = 0;
			else if （j != 0 && j != i && a[i - 1][j - 1].seleted == 0 && a[i - 1][j].seleted != 0 &&
				a[i][j].sum != a[i - 1][j].sum - a[i - 1][j].key）
				a[i][j].seleted = 0;
		}
	}
}
void Output_selected（int N brick**a）		//输出selected金字塔以便检查
{
	for （int i = 0; i <= N - 1; i++） {
		for （int j = 0; j <= i; j++） {
			if （j == 0） {
				for （int k = 0; k < N - i - 1; k++）
					cout << setw（4） << “ “;
			}
			cout << setw（4） << a[i][j].seleted ;
			cout << setw（4） << “ “;
		}
		cout << endl;
	}
	cout << endl;
}
void Max（int N brick**a）		//得到最优路径，标记selected
{
	for （int i = N-1; i >= 0; i--） {		//自下而上 
		for （int j = 0; j <= i; j++） {
			if （i == N-1） {
				a[i][j].sum = a[i][j].key;
			}
			else if （a[i + 1][j].key > a[i + 1][j + 1].key） {		// 左下大于右下 
				a[i][j].sum = a[i][j].key + a[i + 1][j].sum;
				a[i + 1][j].seleted = 1;
			}
			else if （a[i + 1][j].key < a[i + 1][j + 1].key） {		//右下大于左下 
				a[i][j].sum = a[i][j].key + a[i + 1][j + 1].sum;
				a[i + 1][j + 1].seleted = 1;
			}
			else if（a[i + 1][j].key = a[i + 1][j + 1].key）{		//相等 
				a[i][j].sum = a[i][j].key + a[i + 1][j].sum;
				a[i + 1][j].seleted = 1;
				a[i + 1][j + 1].seleted = 1;
			}
		}
	}
	a[0][0].seleted = 1;
}

void Output_result（int N brick**a）		//将最优路径输出，可以得到多条路径
{
	for （int i = 0; i < N; i++） {
		for （int j = 0; j <= i; j++） {
			if （j == 0） {
				for （int k = 0; k < N - i - 1; k++）
					cout << setw（4） << “ “;
			}
			if （i == 0 && j == 0） 
				cout << setw（4） << a[0][0].key;
			else if （a[i][j].seleted == 1） {
				cout << setw（4） << a[i][j].key;
				cout << setw（4） << “ “;
			}
			else if （a[i][j].seleted != 1） {
				cout << setw（4） << “ “;
				cout << setw（4） << “ “;
			}
		}
		cout << endl;
	}
}

int main（）
{
	cout << “请输入金字塔的层数：“ << endl;
	int n choice=0;
	cin >> n;
	brick** a;
	a = new brick*[n];

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件    1859460  2018-06-08 17:30  钻石金字塔.exe

     文件       4151  2018-06-06 00:52  钻石金字塔.cpp

     文件     217088  2019-04-06 12:45  钻石金字塔.docx

----------- ---------  ---------- -----  ----

              2080699                    3