求助，动态规划！

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3096 天前的主题，其中的信息可能已经有所发展或是发生改变。

求哪位大神讲解一下动态规划，或者讲动态规划比较清晰的博客地址。新手实在看不太懂，到现在 01 背包也只是看懂了一点。。云里雾里的

动态

规划

背包

新手

21 条回复 • 2016-05-24 11:15:52 +08:00

mrsatangel

2016-05-22 14:00:42 +08:00

这是在作数模？

wemore

2016-05-22 14:04:10 +08:00 via Android

@mrsatangel 参加竞赛，在题库里遇到很多动态规划题

jiezhi

2016-05-22 14:05:43 +08:00

在高中准备 NOIP 的时候好像做过，现在只记得很难了。

aljun

2016-05-22 14:05:48 +08:00 via iPhone

可以去看看背包九讲

然后我推荐你先搞懂搜索，动归要说起来其实是记忆了搜索的一些树，做了些“剪枝”

kindjeff

2016-05-22 14:05:51 +08:00

找算法的教学 PPT

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

2016-05-22 15:10:22 +08:00

背包问题就是记忆型搜索，深搜和广搜先学好，之后去找「背包九讲」来看看。

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

2016-05-22 15:17:24 +08:00

背包九讲+1

SuperFashi

2016-05-22 15:54:33 +08:00 via Android

竟然有人在 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 也没什么用。
总之背包和区间还好，到时候状压会让你怀疑人生的。