开发者社区> 千锋Python讲堂> 正文

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

简介: Python算法题解:动态规划解0-1背包问题
+关注继续查看

概述

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

定义

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

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

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

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

动态规划

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

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

思路

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

screenshot

当放入物品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=weight[i];j--){//只要背包可以放入就放dp[j]=Math.max(dp[j-weight[i]]+value[i],dp[j]);//比较放入物品之前与放入之后的价值哪个大}}returndp[W];}
复杂度

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

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
部分背包问题
题目描述 给定一个最大载重量为M的卡车和N种食品,有食盐,白糖,大米等。已知第i种食品的最多拥有Wi公斤,其商品价值为Vi元/公斤,编程确定一个装货方案,使得装入卡车中的所有物品总价值最大。输入第一行输入两个整数M和N,用空格隔开第二行到第N+1行每一行输入两个数wi和vi,表示第i种物品的重量和单位价值。
896 0
Mybatis基础: 常见问题与FAQ
Mybatis基础: #{...} 和 ${...} 的区别MyBatis将 #{…} 解释为JDBC prepared statement 的一个参数标记。而将 ${…} 解释为字符串替换。理解这两者的区别是很有用的, 因为在某些SQL语句中并不能使用参数标记(parameter markers)。
724 0
数据结构和算法对python意味着什么?
数据结构和算法对于python而言是他的灵魂;程序是数据结构加上算法来实现的,对于任何一门编程语言都离不开数据结构和算法,但是对于python而言内置了基础的数据结构如列表、字典、集合等,再加上众多包,所以弱化了数据结构和算法的使用。
1791 0
Python数据分析之锁具装箱问题
问题重述 某厂生产一种弹子锁,其槽数高度可以用1到6中取5个来表示。其限制条件是:至少在5个中有3个不同的数;相邻槽的高度相差不能为5。在实际试验中,发现若二锁对应5个槽的高度中有4个相同,另一个差1则可能互开,否则,不可能互开。
905 0
物件捆绑 背包问题 动态规划 求解
  物件捆绑背包问题:给定N元钱,要购买一些器件。器件有主件和附件之分,也即主件可以单独购买,然而购买附件必须购买对应的主件。下表就是一些主件与附件的例子: 主件 附件 电脑      打印机、扫描仪 书柜 图书 书桌          台灯 工作椅 无      把每件物品规定一个重要度,分为5等:用整数1~5表示,第5等最重要。
875 0
砝码称重问题求解:动态规划与母函数方法
  砝码称重问题:设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其质量> syms x; >> f1=(1+x); >> f2=(1+x^2+x^4); >> f3=(1+x^3+x^6); >> f4=(1+x^20); >> expand(f1*f2*f3*f4)>>ans...
1194 0
连续x次奇数(n+2*x)是合数的算法题暴力算法
// 连续6个奇数a,a+2,a+4,a+6,a+8,a+10都是合数,求最小的a // 暴力解法 先上结果,后面贴上代码: 1次连续n=9,连续值个数: 1;耗时: 0ms,总计: 0ms 2次连续n=25,连续值个数: 1;耗时: 0ms,总计: 0ms 3次连续n=91,连续值个数: 1...
689 0
回溯法解决0-1背包问题
问题描述:   有n件物品和一个容量为c的背包。第i件物品的价值是v[i],重量是w[i]。求解将哪些物品装入背包可使价值总和最大。所谓01背包,表示每一个物品只有一个,要么装入,要么不装入。回溯法:   01背包属于找最优解问题,用回溯法需要构造解的子集树。
1261 0
+关注
千锋Python讲堂
Python忠实粉!从业Python已有6年!希望在这里跟大家一起分享我的经验和同伴交流!
59
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载