01背包问题例题讲解 背包问题
【01背包问题例题讲解 背包问题】复杂性分析
时间复杂度:o() 。
因为有多余的子问题 。
辅助空房间:O(1) 。
因为没有额外的数据结构来存储值 。
2.通过自下而上构造临时数组K[][] ， 可以避免重新计算同一个子问题 。方法:在动态编程中 ， 我们将考虑递归方法中提到的相同情况 。在DP[][]表中 ， 让我们将从1到w的所有可能的权重视为列 ， 将权重保持为行 。考虑从1到I的所有值 ， 状态DP[i][j]将表示j-weight的最大值 。因此 ， 如果考虑wi(第I行的权重) ， 可以将其填入所有列wi(权重值> wi) 。
现在可能发生两种情况:
在给定栏中填写作业指导书 。
不要在给定栏中填写作业指导书 。
现在 ， 我们不得不最大限度地考虑这两种可能性 。形式上 ， 如果我们在第j列不填充ith weight ， DP[i][j]的状态将与DP[i-1][j]的状态相同 ， 但如果我们填充weight ， DP[i][j]将等于wi的值+前一行权重为j-wi的列的值 。因此 ， 我们使用这两种可能性中的最大值来填充当前状态 。
以下是上述方法的python代码实现:
def knapSack(W, wt, val, n):K = [[0 for x in range(W + 1)] for x in range(n + 1)]# Build table K[][] in bottom up mannerfor i in range(n + 1):for w in range(W + 1):if i == 0 or w == 0:K[i][w] = 0elif wt[i-1]
推荐阅读
- 汽车在转弯的时候前轮会响,是什么问题呢? 开车拐弯时前轮响怎么回事
- 真心话游戏问题
- 旅游精美句子
- 治疗宝宝湿疹流黄水的问题
- 新飞空调不制热什么问题
- 教育资源平台横幅标语：解决问题透师生伴左右
- 最新微信英文网名男生高端大气 问题
- 小孩子指甲上有白点是什么问题
- 汽车电瓶需要更换预兆 汽车电瓶问题的了解
- 阑尾炎术后会复发吗