01背包问题学习日志

对于这个困扰我很久的问题,当初真的很难,当初勉强会01背包问题,当然是没有理解,感觉很失败,现在算是理解吧背包问题的了所以来发一篇文章,就从最基础的01背包开始吧

先来说一下二维的01背包吧

d[i][j] = max(d[i - 1][j], d[i - 1][j - v[i]] + w[i]);

先说这个状态转移方程之前我就先说一下dp吧,想贪心算法就是以局部最优达到全局最优的目的,但往往局部最优不能达到全局最优,所以说就要一种方法去是每一个状态达到当前最优的状态, 最简单的dp数字三角形(这里选择的是正向往下推),这样在一个新开的数组中储存的第二行中的每一个都是第一行达到当前状态的最大值,而后的每一行都会是上一行达到当前状态的最大值,一直道最后一行,这样只需在最后一行中找到最大值就是从上到下中路径的权值和最大的一个,当然如果从下往上推那样d[1][1]就是最大的。

对于01背包的话,先说说初始化,有两种初始化的方法

1.将d[1][1]初始化为0,其余全部初始化为-INF
2.将d中所有的数组全部初始化为0

这种初始化代表的含义有所不同第一种的含义是所有从最初的状态种转移过来的最优解,第二种的话答案不一定是从第一个转移过来的。

对于01背包的话就是对于一个物品来说有两种状态,要(1)和不要(0)所以叫做01背包,按照前面分析的dp是什么的话就是让每一个阶段达到最优, 对于所有的阶段可以大致按第几个物品分,就是第i种和第i - 1种。

也就是说对于第i(i = (1...n))种的状态总是从第i - 1种的状态转移过来

而对于一个物品如果体积大于总体积那样这个状态只能从上一个状态转移过来即

d[i][j] = d[i - 1][j]

这个就是不要这个物品,但是如果体积满足的话也不一定要这个物品,也就是说在j >= v[i]的情况下(就是当前可用体积大于第i个物品的体积的时候)
判断一下d[i - 1][j] 上一个物品在体积是j的时候是否大于上一个物品体积是d[i - 1][j - v[i]] + w[i] (这个体积依然是j,如果拿的话也就是说一定有v[i]的体积用来放价值为w[i]的物品,然后再加上体积是体积j - v[i]的时候上一个物品的最大的价值)将这两个中间的最大的数给d[i][j]就是再第i个物品体积是j的情况下最大价值就能算出来了

当然也可以改成一维的,这里就不在此具体介绍了

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注