Python算法题解:动态规划解0-1背包问题

发布时间:2020-08-08 12:04:23 作者:千锋Python唐小强
来源:ITPUB博客 阅读:248

概述

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

定义

我们有 n 种物品,物品 j 的重量为wj,价格为pj。
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。

如果限定每种物品只能选择0个或1个,则问题称为 0-1背包问题

如果限定物品j最多只能选择bj个,则问题称为 有界背包问题

如果不限定每种物品的数量,则问题称为 无界背包问题

动态规划

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。

思路

举例,令物品数量N=5,背包所能承受的最大重量为W=10,物品与价格的对应关系如下表左三列所示。

Python算法题解:动态规划解0-1背包问题

当放入物品a时,在背包所能承受的重量内,计算背包拥有的物品总价格,并进行标记,如表格第一行所示,当背包所能承受的重量大于等于2时,都可以放入物品a,背包拥有的物品总价格为6。

接着我们放入物品b,放入之前,一是要判断背包是否所能承受其重量,二是判断放入之后与放入之前拥有的物品总价格哪个最大,如表格第二行所示,当背包所能承受的重量大于等于2时,都可以放入物品b,但是,物品b在背包容量为[2,3]的时候,放入之后的总价格3不如放入之前的总价格6大,所以不放入。

当背包所能承受的重量等于4时,放入物品b后,背包所能承受的重量4减去物品b的重量2后,剩余的所能承受的重量2还可以放入物品a,此时背包拥有的物品总价格为物品a和物品b的总价格之和,即为9,大于放入之前的物品总价格6,所以此时背包拥有的物品总价格最大为9。

分析可知,在一层循环遍历下,我们需要一个一维数组保存背包所能承受的最大重量与其拥有的物品总价格,并不断更新。

代码

Copy/***0-1背包问题**@paramN物品数量*@paramW背包容量*@paramweight物品重量*@paramvalue物品价格*@return最大价值*/privatestaticinttraceBack(intN,intW,int[]weight,int[]value){int[]dp=newint[W+1];//范围[0,W]当前背包容量对应的物品总价值for(inti=0;i<N;i++){//一件、一件的向包中放入每件物品for(intj=W;j>=weight[i];j--){//只要背包可以放入就放dp[j]=Math.max(dp[j-weight[i]]+value[i],dp[j]);//比较放入物品之前与放入之后的价值哪个大}}returndp[W];}

复杂度

显而易见,算法需要的时间复杂度为O(nW),空间的消耗(即所需的一维数组)为O(W)。

有不清楚的地方,伙伴们可以留言,更多的Python相关教程也会继续为大家更新!

推荐阅读:
  1. PHP如何实现背包问题的动态规划
  2. JS基于贪心算法解决背包问题示例

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python 算法 题解

上一篇:直播回顾 丨TBase多中心多活与高可用方案实践

下一篇:JDBC读取数据优化-fetch size

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》