。

平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。

我会一直往里填充内容哒#xff01;

Halo这里是Ppeua。

平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。

个人主页主页链接

求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。

输入格式

分析01背包问题的特点有N件物品背包容积是V每件物品只能拿0或不拿1所以称为01背包问题.

将问题分析,当决定第i件拿与不拿的时候,表达式为:此时背包价值max(背包没拿第i件物品的价值,拿了第i件物品的价值)

状态计算为f[i][j],其中i为第几件物品,j为此时背包的容量

因为直接计算选第i件物品比较难计算,所以我们将选第i件物品的价值转换为,不选第i件物品的价值,并令其背包容积减去第i件物品的v再加上其价值w

所以我们的状态方程就为:f[i][j]max(f[i-1],f[i-1][j-v]w)

代码实现:

w[i]);//在拿i-1件物品其容量为j-vi时放入物品的最大值

}}cout

观察.f[i][j]的变换形式,每次计算只用到了上一层i,j,所以我们可以将i这一维给删了,变成这种形式

int

w[i]);//滚动数组优化从后向前遍历这样第一个的结果用到的是上一层的数据}}cout

f[m];

f[j-v[i]]w[i],用到的是这一层已经计算的数据(因为j是从小开始算的,也就是说从小的j开始就会把上一次计算的j给覆盖了,而后面要用到的是上面一层i-1的数据,而不是i)

所以我们为了避免这种情况,使用i-1的数据,我们从后往前遍历,这样每一次计算j时,用的就是i-1层的数据,与上文所述一致

代码实现:

w[i]);//滚动数组优化从后向前遍历这样第一个的结果用到的是上一层的数据}}cout

f[m];

求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。

输入格式

完全背包问题是01背包问题的升级版.每件物品不再只能拿一件,而可以无限拿(在容量允许的情况下)

将问题分析,当决定第i件拿K件,表达式为:此时背包价值max(背包没拿第i件物品的价值,拿了K*第i件物品的价值)

所以这里的状态表示的集合为:从前i件物品拿K件,且总体积不超过j

状态计算为f[i][j],其中i为第几件物品,j为此时背包的容量

因为直接计算拿第i件k个比较难计算,所以我们将选第i件物品的价值转换为,不选第i件物品的价值,并令其背包容积减去第i件物品的K*v再加上其价值K*w

代码实现:

k0;k*v[i]j;k){f[i][j]f[i-1][j];if(jk*v[i])f[i][j]max(f[i][j],f[i-1][j-k*v[i]]k*w[i]);}}}coutf[n][m];

这和01背包问题的朴素做法几乎一模一样,但这里的时间复杂度为n^3,所以我们得优化一下,不然就TLE了

优化:

对于f[i,j-v]的含义是:将JK*V时,我们先将第i个物品放入背包,之后再去找当前容量下能放入的最大价值的东西,之后再加上w,这时候就可以不用考虑具体放几件了,

最后也就变成了f[i][j]Max(f[i-1][j],f[i][j-v]w)

代码实现:

j0;jm;j){f[i][j]f[i-1][j];if(jv[i])f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);//表示已经选入第i层

}}coutf[n][m];

因为还是N^2,观察这个表达式,和01背包问题很想,且也只用到了i-1层

所以可以用滚动数组优化,删掉一维即可,因为这里计算max的时候用的式i

代码实现:

jv[i];jm;j){f[j]max(f[j],f[j-v[i]]w[i]);//表示已经选入第i层

}}coutf[m];

若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。

若以上内容有任何问题欢迎在评论区指出。

若对以上内容有任何不解都可私信评论询问。

诸君山顶见