一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1359|回复: 13
收起左侧

[树/链表/图] 一道似乎用DP也不能解决的题: diamond mine

[复制链接] |试试Instant~ |关注本帖
siriuxy 发表于 2016-10-8 09:08:02 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近做到一道很难的题目,用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)?
larry_cn 发表于 2016-10-12 04:29:17 | 显示全部楼层
https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

看advanced 部分
回复 支持 1 反对 0

使用道具 举报

zj45499 发表于 2016-10-8 11:22:07 | 显示全部楼层
我也想不出来..
不过感觉可以写个brute force的算法来verify一下...
回复 支持 反对

使用道具 举报

 楼主| siriuxy 发表于 2016-10-8 11:44:41 | 显示全部楼层
zj45499 发表于 2016-10-8 11:22
我也想不出来..
不过感觉可以写个brute force的算法来verify一下...

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

使用道具 举报

stellari 发表于 2016-10-9 05:45:06 | 显示全部楼层
这种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是正确的方向,但是简单地分为两次使用的思路则不可行。你不妨再考虑考虑
回复 支持 反对

使用道具 举报

dukemon7 发表于 2016-10-9 08:48:39 | 显示全部楼层
dp是可解的,但是状态不是二维,朴素dp是四维,可优化到三维解决,你可以再想想
回复 支持 反对

使用道具 举报

33847682 发表于 2016-10-9 11:39:17 | 显示全部楼层
dukemon7 发表于 2016-10-9 08:48
dp是可解的,但是状态不是二维,朴素dp是四维,可优化到三维解决,你可以再想想

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

使用道具 举报

dukemon7 发表于 2016-10-10 02:50:33 | 显示全部楼层
33847682 发表于 2016-10-9 11:39
求问为啥是4维?三维解决不了嘛?前两维是坐标 最后一维表示拿或者不拿这格的钻石所能得到的钻石最大值  ...

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

使用道具 举报

33847682 发表于 2016-10-10 05:56:10 | 显示全部楼层
dukemon7 发表于 2016-10-10 02:50
还是会有楼主的问题,你只加了一维当前节点取或者不取的结果,你怎么去计算一条完整线路是否有重复呢?三 ...

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

使用道具 举报

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

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

使用道具 举报

33847682 发表于 2016-10-12 06:53:49 | 显示全部楼层
dukemon7 发表于 2016-10-12 04:19
抱歉前两天没上地里,你就想成是去的时候走两条路,一直走到终点就好了,这样就不难想出来了

就是 开一个三维数组存两条路线各自能取得diamond的最大值 同时要求两个路线不能相交?[row][col1][col2]像这样?
回复 支持 反对

使用道具 举报

dukemon7 发表于 2016-10-12 08:34:30 | 显示全部楼层
33847682 发表于 2016-10-12 06:53
就是 开一个三维数组存两条路线各自能取得diamond的最大值 同时要求两个路线不能相交?[row][col1][col2] ...

存两条线一共能取到多少,所以最朴素的是四维,表示两条路走到哪两个点了,这时候的最大值,三维的表示法你需要再想想...你写的这个不行...另外不一定是不能相交,只是相交的时候只能记录一次
回复 支持 反对

使用道具 举报

33847682 发表于 2016-10-12 10:00:53 | 显示全部楼层
dukemon7 发表于 2016-10-12 08:34
存两条线一共能取到多少,所以最朴素的是四维,表示两条路走到哪两个点了,这时候的最大值,三维的表示法 ...

哦哦 我懂你的意思了 就是
dp[i1][j1][i2][j2]=max(dp[i1-1][j1][i2][j2],dp[i1][j1-1][i2][j2])+max(dp[i1][j1][i2-1][j2],dp[i1][j1][i2][j2-1]+val[i1][j1]+(i1==i2&&j1==j2)?0:val[i2][j2]
这样对嘛?
回复 支持 反对

使用道具 举报

yuwang1986s 发表于 2016-10-12 12:24:58 | 显示全部楼层
DP 可以解决的,经典的dp问题。去top coder看
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 17:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表