一道似乎用DP也不能解决的题： diamond mine

最近做到一道很难的题目，用DP并不能解决。请先读题:

http://imgur.com/a/58bK3

提出DP做法的同学，我问你一个问题，如果从起点到终点的时候是取的能采集最多diamond的情况，那么这是否会破坏从钟点回到起点的路径，导致回程的路上采集不到很多diamond？因为每一个采集路径都会对地图上剩余diamond 的分布造成影响，那么采用这种greedy的做法如何才能证明 Max(start->end, new map)+Max(end->start, map after max(s->e)) = Max(start->end->start, new map)?

https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

看advanced 部分

这种greedy算法是不行的。这就好像打10瓶保龄球，比如第一球打倒了正中间的8个，但是一边剩下1个，那第二球无论如何都只能打到1个，最后总成绩为9；而如果第一球打倒左边的6个，第二球打倒右边的4个，虽然每次都不是最优，但是最后总成绩为10.

具体到这个题，可以考虑下面的例子：
0 0 0 1 1 0
1 0 0 1 1 0
1 0 0 0 1 0
1 0 0 0 1 0
0 0 0 0 1 1

这个例子中，Max(start->end, new map)=7，走完以后变成：
0 0 0 1 1 0
0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0

此时无论怎么走回去，都只能最多再拿2块钻石，也就是说，这样走最多拿7 + 2 = 9块。地图上还会剩下2块钻石无法拿走。

而如果开始一直向下走，走到左下角再向右：
0 0 0 1 1 0
0 0 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 0 0

这时虽然只拿了5块钻石，但是回程时则同样可拿到5块，最后能拿到10块钻石。

用DP是正确的方向，但是简单地分为两次使用的思路则不可行。你不妨再考虑考虑

33847682 发表于 2016-10-9 11:39
求问为啥是4维？三维解决不了嘛？前两维是坐标 最后一维表示拿或者不拿这格的钻石所能得到的钻石最大值  ...

还是会有楼主的问题，你只加了一维当前节点取或者不取的结果，你怎么去计算一条完整线路是否有重复呢？三维可以解的，我说的四维的优化其实就是这个，但是状态的划分不一样，你别考虑做两次，把来回的线路一起加到状态上考虑看看，这样会容易想到一些

我也想不出来..
不过感觉可以写个brute force的算法来verify一下...

zj45499 发表于 2016-10-8 11:22
我也想不出来..
不过感觉可以写个brute force的算法来verify一下...

因为地图的长宽最高为100，如果用brute force的话会有2^100*2^100种可能性，大约是1.6*10^60，感觉这个量用计算机可能不太现实……

dp是可解的，但是状态不是二维，朴素dp是四维，可优化到三维解决，你可以再想想

dukemon7 发表于 2016-10-9 08:48
dp是可解的，但是状态不是二维，朴素dp是四维，可优化到三维解决，你可以再想想

求问为啥是4维？三维解决不了嘛？前两维是坐标 最后一维表示拿或者不拿这格的钻石所能得到的钻石最大值 然后再反过来算一遍
不知道这个思路对不对？

dukemon7 发表于 2016-10-10 02:50
还是会有楼主的问题，你只加了一维当前节点取或者不取的结果，你怎么去计算一条完整线路是否有重复呢？三 ...

貌似是这样的 要是分开考虑确实机会像楼主一样 应该全局考虑最佳 可是 怎么把来回路线考虑在一起啊？求列个状态转移方程

33847682 发表于 2016-10-10 05:56
貌似是这样的 要是分开考虑确实机会像楼主一样 应该全局考虑最佳 可是 怎么把来回路线考虑在一起啊？求列 ...

抱歉前两天没上地里，你就想成是去的时候走两条路，一直走到终点就好了，这样就不难想出来了