我试图解决以下问题,但无法开发算法或方法.我已经研究了几个小时,并试图将问题映射到"最短路径"图形/矩阵问题或动态编程问题,但是它没有成功.
我相信stackoverflow是发布此而不是cs.stackexchange.com的正确网站.在downvoting之前,请发表评论并告诉我,如果不是这样,我将删除该问题或将其移至另一个网站:)
给定宽度为w的网格,h为高度.网格的每个单元代表一个潜在的建筑物,我们将在该网格中添加"n"个建筑物.目标是使所有地段中最远的地方尽可能接近建筑物.给定输入n(即要放置在该批次中的建筑物数量),确定建筑物放置以最小化距离建筑物最远的空地段的距离.运动受限于水平和垂直,即不需要对角线运动.
例如,w=4, h=4 and n=3.最佳网格布置可将任何批次设置在建筑物的两个单位距离内.这个案子的答案是2.
"0"表示最佳建筑物放置,并且在这种情况下,每个单元到最近建筑物的所有最短距离的最大值是"2".
1 0 1 2
2 1 2 1
1 0 1 0
2 1 2 1
以上代表一种最佳解决方案,可以更像上述旋转的阵列作为示例.以上是最佳解决方案,因为在3个建筑物(n = 3)中,一个建筑物放置在索引(0,1)处,第二个建筑物放置在(2,1)处,第三个建筑物放置在(2,3)处.每次水平和/或垂直移动时,周围的水平和垂直距离显示为1和2,加1.请再次注意,不允许对角线移动:
1 ? 0 ? 1 ? 2
?
2 ? 1 ? 2 ? 1
? ?
1 ? 0 ? 1 ? 0
? ?
2 ? 1 ? 2 ? 1
其他例子:
例1)
w=3, h=3, n=2
必须最佳地放置两个建筑物(零).这种情况的最佳方案之一是:
01
11
10
0 ? 1
?
1 1
?
1 ? …在观看下面的 MIT 6.001 课程视频时，教师在 28:00 将此算法标记为迭代。但是，在 30.27，他说这个算法和实际的“递归”算法都是递归的。该函数使用基本情况调用自身，那么这个迭代如何？
https://www.youtube.com/watch?v=dlbMuv-jix8&list=PLE18841CABEA24090&index=2
private int iterativeSum(int x, int y)
{
System.out.println("x "+x+" y "+y);
if(x == 0)
{
return y;
}
return iterativeSum(--x, ++y);
}