典型的01背包问题

发布时间:2022-09-16 20:42:10
贴主:小朝啦啦啦
热度:9
正在讨论:P2884 - 停车场 题目传送门

小朝啦啦啦 2022-09-16

//由于这是典型的背包问题我就用背包的方式讲了

题目就是说有N件物品和一个容量为v的背包。放入第i件物品小号的费用是Ci,得到的价值是Wi,要找到一种方法使的放入背包的物品总和最大。

由于每种物品只有一件,只有两种选择:放或者不放。那么我们可以思考:“将前 i 件物品放入容量为 v 的背包中”这个子问题,若只考虑第 i 件物品的策略(放或不放),那么就可以转化为一个只和前 i − 1 件物品相关的问题。如果不放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”,价值为 F[i − 1, v];如果放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − Ci 的背包中”,此时能获得的最大价值就是 F[i − 1, v − Ci] 再加上通过放入第 i 件物品获得的价值 Wi

所以我们可以得到转移方程为dp[i, v] = max{dp[i − 1, v], dp[i − 1, v − Ci] + Wi}

知道了这个方程之后我们很显然知道要开一个大小为v*v的二维数组,我们浅叫这个数组为dp。我们可以看到dp数组需要很大,至少超过2行!那么我们想一想可不可减少行数呢?

首先我们知道,d[i][j]的值只和它的上一种状态有关,即dp[i-1][j],也就是第i行的dp值,只与第i-1行有关,我们通过这条性质,可以将dp数组减少到两行即可,也就是滚动数组优化01背包!

再深入研究发现dp数组可以变成一维,怎么做呢?设dp[v]表示前i种物品(全部物品或者部分物品)放入一个容量为v的背包可以获得的最大价值,这样转移方程就可以写成dp[v]=max(dp[v],dp[v-w[i]]+c[i])

(4)

小朝啦啦啦 2022-09-16

三种写法我都有开源可以去看看

(1)


Copyright 2016 - 2022 XUJC ACM Team
闽ICP备2020022076号-1