求助，动态规划！

V2EX = way to explore

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

For Existing Member Sign In

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 3627 days ago, the information mentioned may be changed or developed.

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

动态

规划

背包

新手

21 replies • 2016-05-24 11:15:52 +08:00

mrsatangel

May 22, 2016

这是在作数模？

wemore

May 22, 2016 via Android

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

jiezhi

May 22, 2016

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

aljun

May 22, 2016 via iPhone

可以去看看背包九讲

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

kindjeff

May 22, 2016

找算法的教学 PPT

changwei

May 22, 2016

楼主，我现在 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

May 22, 2016

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

xjx0524

May 22, 2016

@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]。
比较大于号左右两边的式子，哪个大就用哪个喽

xxm459259

May 22, 2016

背包九讲+1

SuperFashi

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