1
mrsatangel 2016-05-22 14:00:42 +08:00
这是在作数模?
|
2
wemore OP @mrsatangel 参加竞赛,在题库里遇到很多动态规划题
|
3
jiezhi 2016-05-22 14:05:43 +08:00
在高中准备 NOIP 的时候好像做过,现在只记得很难了。
|
4
aljun 2016-05-22 14:05:48 +08:00 via iPhone
可以去看看背包九讲
然后我推荐你先搞懂搜索,动归要说起来其实是记忆了搜索的一些树,做了些“剪枝” |
5
kindjeff 2016-05-22 14:05:51 +08:00
找算法的教学 PPT
|
6
changwei 2016-05-22 14:43:39 +08:00
楼主,我现在 01 背包问题都是云里雾里的啥都没弄明白,就是判断的时候
for(j=0;j<m+1;j++) for(i=0;i<n+1;i++) { if(j<w[i]) { c[i][j]=c[i-1][j]; continue; }else if(c[i-1][j-w[i]]+p[i]>c[i-1][j]) c[i][j]=c[i-1][j-w[i]]+p[i]; else c[i][j]=c[i-1][j]; } 这里 j<w[i]和 c[i-1][j-w[i]]+p[i]>c[i-1][j]这两个条件我没明白是判断什么的,求告知,谢谢= = |
7
towser 2016-05-22 15:10:22 +08:00
背包问题就是记忆型搜索,深搜和广搜先学好,之后去找「背包九讲」来看看。
|
8
xjx0524 2016-05-22 15:15:58 +08:00
@changwei 首先你要知道( i, j )这个状态表示背包容量为 j 时前 i 个物品所能达到的最大价值。
j<w[i]意思是第 i 个物品容量 w[i]大于当前背包容量 j ,所以不选物品 i ,当前最大价值 c[i][j]=c[i-1][j] c[i-1][j-w[i]]+p[i]>c[i-1][j],大于号右边部分意义和上面一样,代表不选第 i 个物品能达到的最大价值 左边部分表示选上第 i 个物品的最大价值,所以要看( i-1, j-w[i])这个状态(意思是前 i-1 个物品里,背包容量为 j-w[i]时的最大价值),这样把容量为 w[i]的物品 i 放进去刚好达到( i, j )这个状态,然后在加上物品 i 的价值 p[i]。 比较大于号左右两边的式子,哪个大就用哪个喽 |
9
pandachow 2016-05-22 15:17:24 +08:00
背包九讲+1
|
10
SuperFashi 2016-05-22 15:54:33 +08:00 via Android 1
竟然有人在 V2EX 问算法题,吓到。
先推荐个神犇的博客 hzwer.com DP 的最最主要的部分就是在于状态转移,我们需要求出如何从上一个状态转移到下一个状态,也就是转移方程。 例如背包问题,有一维和二维两种方式,本质都是一样的,但是二维比较好理解,我来说一下。 假设 n 个物品,这 n 个物品的大小在一个数组 weight[n]里面,背包最大装 m ,数组 dp[i][j], i 表示输入中的前 i 个物品, j 表示背包此时大小, dp[i][j]表示有 i 个物品且背包大小为 j 时最多能装多少东西(或者大小,都是一样的)。 首先对某个物品来说,背包的大小肯定不能小于物品大小,否则装不进去了,也就是 dp[i][]中 weight[i] >= j 。接下来,我们在可以想出,要是想装这个物体, dp[i][j]就是 dp[i - 1][j - weight[i]] + 1 ,但实际上,有的物品不装反而最后能满足的更多,那么我们还要判断是 dp[i - 1][j]大还是 dp[i - 1][j - weight[i]] + 1 大,表示到底装不装这个物品大。 这时候还没完,我们发现,在 weight[i] < j 的这时候,其实我们也可以不装此时这个物品,因为装不进去,但是可以把以前能装的的物品装进去,也就是直接赋为 dp[i - 1][j]。 然后跑个两层 for 就好了,最后 dp[n][m]就是答案。 好好自己想想为什么,不要看到题解似懂非懂就做, AC 也没什么用。 总之背包和区间还好,到时候状压会让你怀疑人生的。 |
11
GtDzx 2016-05-22 16:09:58 +08:00
可以去看看 http://hihocoder.com/discuss/question/2822 后半部分的教学篇
PS 题目需要注册登录 |
12
lechain 2016-05-22 16:18:25 +08:00 via Android
理解几个概念。 dP 的条件:问题是否能分解为子问题 子问题的求解是否无后效性 还有 最重要的是理解状态 和 转移。还有多做题就好了
|
13
lsylsy2 2016-05-22 16:19:27 +08:00
背包九讲+2
虽然我不是看它学的,但是写的真的不错 |
14
changwei 2016-05-22 17:10:00 +08:00
@xjx0524 啊,听你这么一说好像明白了好多(⊙0⊙)还有有一个疑问就是为什么两个 for 的循环结束条件是 m+1 和 n+1 呢?还有这两层循环结束之后, c[][]数组里面是 c[m][n]存的是最大价值还是 c[m+1][n+1]呢?为什么是这样?谢谢谢解答= =
|
16
binux 2016-05-22 18:50:04 +08:00
动态规划就是带结果缓存的 f(n) = g(f(n-1))
|
17
newton108 2016-05-22 19:04:53 +08:00
mit 6.006 6.046j
|
18
yhylord 2016-05-22 21:18:53 +08:00
@SuperFashi 看黄学长的 blog 真是充满励志……从第一条到最后一条……
|
19
linux40 2016-05-23 08:25:58 +08:00 via Android
算法导论上的动态规划讲得很好。
|
20
wizardforcel 2016-05-23 12:48:51 +08:00 via Android
看成带 cache 的递归调用。
背包的转移方程是二维的,语义理解起来也有点困难,不如先找些一维的来做。 |
21
MouCai 2016-05-24 11:15:52 +08:00
动态规划什么的,这个我认为我可以插上话啦,看这个[文章]( https://github.com/MouCai/blog/issues/2), 讲的 Levenshtein distance 算法,就是利用动态规划的思想解决问题的。
|