V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
wemore
V2EX  ›  程序员

求助,动态规划!

  •  
  •   wemore · 2016-05-22 13:51:51 +08:00 via Android · 3675 次点击
    这是一个创建于 3092 天前的主题,其中的信息可能已经有所发展或是发生改变。
    求哪位大神讲解一下动态规划,或者讲动态规划比较清晰的博客地址。新手实在看不太懂,到现在 01 背包也只是看懂了一点。。云里雾里的
    21 条回复    2016-05-24 11:15:52 +08:00
    mrsatangel
        1
    mrsatangel  
       2016-05-22 14:00:42 +08:00
    这是在作数模?
    wemore
        2
    wemore  
    OP
       2016-05-22 14:04:10 +08:00 via Android
    @mrsatangel 参加竞赛,在题库里遇到很多动态规划题
    jiezhi
        3
    jiezhi  
       2016-05-22 14:05:43 +08:00
    在高中准备 NOIP 的时候好像做过,现在只记得很难了。
    aljun
        4
    aljun  
       2016-05-22 14:05:48 +08:00 via iPhone
    可以去看看背包九讲

    然后我推荐你先搞懂搜索,动归要说起来其实是记忆了搜索的一些树,做了些“剪枝”
    kindjeff
        5
    kindjeff  
       2016-05-22 14:05:51 +08:00
    找算法的教学 PPT
    changwei
        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]这两个条件我没明白是判断什么的,求告知,谢谢= =
    towser
        7
    towser  
       2016-05-22 15:10:22 +08:00
    背包问题就是记忆型搜索,深搜和广搜先学好,之后去找「背包九讲」来看看。
    xjx0524
        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]。
    比较大于号左右两边的式子,哪个大就用哪个喽
    pandachow
        9
    pandachow  
       2016-05-22 15:17:24 +08:00
    背包九讲+1
    SuperFashi
        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 也没什么用。
    总之背包和区间还好,到时候状压会让你怀疑人生的。
    GtDzx
        11
    GtDzx  
       2016-05-22 16:09:58 +08:00
    可以去看看 http://hihocoder.com/discuss/question/2822 后半部分的教学篇
    PS 题目需要注册登录
    lechain
        12
    lechain  
       2016-05-22 16:18:25 +08:00 via Android
    理解几个概念。 dP 的条件:问题是否能分解为子问题 子问题的求解是否无后效性 还有 最重要的是理解状态 和 转移。还有多做题就好了
    lsylsy2
        13
    lsylsy2  
       2016-05-22 16:19:27 +08:00
    背包九讲+2
    虽然我不是看它学的,但是写的真的不错
    changwei
        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]呢?为什么是这样?谢谢谢解答= =
    xjx0524
        15
    xjx0524  
       2016-05-22 18:44:57 +08:00 via Android
    @changwei 那是小于号啊朋友。。。
    for(j=0;j<m+1;j++)
    j 最大是 m 啊
    binux
        16
    binux  
       2016-05-22 18:50:04 +08:00
    动态规划就是带结果缓存的 f(n) = g(f(n-1))
    newton108
        17
    newton108  
       2016-05-22 19:04:53 +08:00
    mit 6.006 6.046j
    yhylord
        18
    yhylord  
       2016-05-22 21:18:53 +08:00
    @SuperFashi 看黄学长的 blog 真是充满励志……从第一条到最后一条……
    linux40
        19
    linux40  
       2016-05-23 08:25:58 +08:00 via Android
    算法导论上的动态规划讲得很好。
    wizardforcel
        20
    wizardforcel  
       2016-05-23 12:48:51 +08:00 via Android
    看成带 cache 的递归调用。

    背包的转移方程是二维的,语义理解起来也有点困难,不如先找些一维的来做。
    MouCai
        21
    MouCai  
       2016-05-24 11:15:52 +08:00
    动态规划什么的,这个我认为我可以插上话啦,看这个[文章]( https://github.com/MouCai/blog/issues/2), 讲的 Levenshtein distance 算法,就是利用动态规划的思想解决问题的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2950 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 02:51 · PVG 10:51 · LAX 18:51 · JFK 21:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.