首先是问题，
假设一个整数可以表示为一个完美的球体，其中球体的值等于它包含的整数。球体被组织成一个四面体金字塔，其中 N = 边长，N 在 1 到 15 之间。选择球体的(可能为空的)子集，使它们的值之和最大化。请注意，球体可以保持负值，因此不一定需要拾取每个球体。我们不想破坏金字塔的组织，所以我们不能在没有先拿走它上面的球体的情况下拿走任何一个球体。
输入格式:
第 1 行:整数 N
第 2 行:N(N+1)/2+1
输出格式:
第 1 行:一个整数，可实现的最大值之和
示例输入:
3
5
-2 -7
-3
1 0 8
0 3
2
示例输出:
8
到目前为止，这是我所理解的示例解决方案:
最佳解决方案在下图中以粗体显示。取 1 并不明智，因为那需要取 -2，从而减少总数。应该取 8、3 和 2，因为它们超过 -3 和 -7。
我的问题是，
如何存储输入以便保留正确的顺序？或者我什至需要？我正在尝试使用队列，但我的程序变得非常冗长，因为我必须找到每个可能路径的总和，然后比较每个总和以找到最大值。我也很难将数据分解成正确的模式，所以我不会重新计算一个数字或不按顺序取一个。有没有更有效的方法来做到这一点？ Dijkstra 的算法在这种情况下有什么用吗？如果是这样，那又如何呢？任何帮助是极大的赞赏!!
最佳答案
我会使用 3 维数组。要使用您的示例:
A[0][0][0] = 5
A[1][0][0] = -2
A[1][1][0] = -3
A[1][0][1] = -7
A[2][0][0] = 1
A[2][1][0] = 0
A[2][2][0] = 2
A[2][0][0] = 0
A[2][1][0] = 3
A[2][0][0] = 8
“上面”关系只是索引算法的问题:[ia, ja, ka] 在 [ ia+1, ja, ka], [ia+1, j a+1, ka] 和 [ia+1, ja, ka>+1].
关于c++ - 如何在整数四面体中找到具有最小可能路径的最大和？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31282393/