首页 » 技术分享 » 北邮 招聘矿工(记忆化 or dp)

北邮 招聘矿工(记忆化 or dp)

　
评论关闭　784次浏览

本博主仅提供自己想法的分享，勿抄袭

题目

现在你的任务是从金字塔的顶端向金字塔的底端收集钻石，并且尽可能收集价值高的钻石，但是只能从一块砖斜向左下或斜向右下走到另一块砖上，如从上图从用红色A标记的砖走向用蓝色B标记的砖上。富翁希望heimengnan找到一个收集最高价值钻石的路线，并且把可能收集的最大价值告诉富翁。heimengnan想了半天也没想出好方法，聪明的你能帮助他吗？
在这里插入图片描述

分析

首先查看深度搜索的过程（如下图），我们可以发现每一条路径上的值都有重复计算的值，那么采取记忆化搜索即可。
在这里插入图片描述
我们将上述结构存储为以下形式
在这里插入图片描述
那么原图每一个点都有两个向下走的方向，那么我们新的图可将向下走类比原图向左走，向右下走类比原图向右走，那么即可实现存储结构的转换。
此外，使用一个数组进行存储每一行的价值，按顺序从上到下，从左到右存储（如下图）。
在这里插入图片描述
那么如何实现一次遍历得出最优结果呢？
当然离不开存储值。

  1. 如果只有两层三个值：
    在这里插入图片描述
    毫无疑问，5 + 1 = 6, 5 + 3 = 8，价值8最大

  2. 只有三层：
    在这里插入图片描述
    那么很明显，我们可以直接俄借助刚才已经计算过的到达a[2]最大值为6，到达a[3]最大值为8，那么计算到达a[4 to 6]就可以直接利用这两个最大值，得到如下表格形式：
    在这里插入图片描述

  3. 那么，思路很明显了。我们只需要遍历每一个值，如节点a[i],我们需要更新子节点a[i + down]和a[i + rightdown]的值，并且每次赋值时，如果是可以增大价值则更新，否则不更新。

数据结构

  1. 建立三个数组
value[]    存储价值
beifenvalue[]   价值备份
fangxiang[]    方向（为0表示value[i]被正上方节点更新，1表示value[i]被左上方节点更新）
  1. 表达式
if (value[i] + beifenvalue[i + cnt] > value[i + cnt]) {
	value[i + cnt] = value[i] + beifenvalue[i + cnt];
	fangxiang[i + cnt] = 0;
}
if (value[i] + beifenvalue[i + cnt + 1] > value[i + cnt + 1]) {
	value[i + cnt + 1] = value[i] + beifenvalue[i + cnt + 1];
	fangxiang[i + cnt + 1] = 1;
}

样例实现过程

在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	int cengshu, mbig = 0,exit;
	cin >> cengshu;	//输入层数
	int num = (cengshu + 1) * cengshu / 2, cnt = 1,* value = new int[num],* beifenvalue = new int[num],* fangxiang = new int[num];  //num表示价值物品个数,三个数组分别存储价值，备份价值，最大值指向
	//数据输入
	for (int i = 1; i <= num; cin >> value[i], beifenvalue[i] = value[i], fangxiang[i] = 0, ++i);
	//遍历一遍即可
	for (int i = 1,start = 2; i <= num;i++) {
		if (i < num - cengshu) {
			if (start <= i) {
				cnt++;
				start = i + cnt;
			}
			if (value[i] + beifenvalue[i + cnt] > value[i + cnt]) {
				value[i + cnt] = value[i] + beifenvalue[i + cnt];
				fangxiang[i + cnt] = 0;
			}
			if (value[i] + beifenvalue[i + cnt + 1] > value[i + cnt + 1]) {
				value[i + cnt + 1] = value[i] + beifenvalue[i + cnt + 1];
				fangxiang[i + cnt + 1] = 1;
			}
		}
		else if (mbig < value[i]) {
			mbig = value[i];
			exit = i;
		}
	}
	//寻找路径并输出
	string route = "";
	for (int i = exit; cnt != 0; route = (to_string(i) + " ") + route,(i = (fangxiang[i] && i != 1) ? i - cnt - 1 : i - cnt),cnt--);
	route = "1 " + route;
	cout<<"路径为："<< route << endl << "最大值为：" << mbig << endl;
}

运行结果

在这里插入图片描述

转载自原文链接, 如需删除请联系管理员。

原文链接：北邮 招聘矿工(记忆化 or dp)，转载请注明来源！

赞 0