解决 01 背包问题的贪婪算法的 Python 实现
一、背包问题
01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。如果选择将其放入背包中,由于不清楚之前放入的物品占据了多大的空间,需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
二、求解思路
当遇到这样的问题,我们可以换一种角度去思考,假设在一个100m3的房子里面,现在要将房子装满,同时要保证放入的物品个数最多以及装入的东西最重,现在身边有铁球和棉花,请问大家是放铁球进去好呢还是放棉花进去好呢?显而易见,放入铁球进去是最优选择。但是原因是什么呢?很简单,就是因为铁球的密度较大,相同体积的铁球和棉花相比,铁球更重。 不过前提是放入第一个铁球时,铁球的体积V1小于等于100m3 ;放入第二个铁球时,铁球的体积V2 小于等于(100-V1)m3;……;放入第n个铁球时,铁球的体积小于等于(100- ∑n1Vn-1)m3 ,要是第n个铁球的体积大于(100- ∑n1Vn-1)m3 ,还真是不如放点单位体积更轻的棉花进去,说的极端点就是所有铁球的体积都大于100m3 ,还真不如随便放入点棉花进去合算。所以总是放铁球进去,不考虑是否放入棉花,容易产生闲置空间,最终会得不到最优选择,可能只是最优选择的近似选择。 现在再次回到背包问题上,要使得背包中可以获得最大总价值的物品,参照铁球的例子我们可以知道选择单位重量下价值最高的物品放入为最优选择。但是由于物品不可分割,无法保证能将背包刚好装满,最后闲置的容量无法将单位重量价值更高的物品放入,此时要是可以将单位重量价值相对低的物品放入,反而会让背包的总价值和单位重量的价值更高。假设现在背包的剩余总重量为5kg,存在一个4kg价值为4.5的物品,一个3kg价值为3的物品,一个2kg价值为2的物品,很显然将3kg和2kg的物品放入背包中所获得的价值更高,虽然没有4kg的物品单位重量的价值高。因此通过贪心算法求解01背包的问题可能得不到问题的最优解,得到的是近似最优解的解。 创建一个物品对象,分别存在价值、重量以及单位重量价值三种属性。
以下以单位重量价值角度分析:
import json
def dictsum(list, keyname):
num = 0
for item in list:
num += item[keyname]
return num
class Greedy():
def __init__(self,data,maxWeight):
self.maxWeight=maxWeight
self.dataList=sorted(self.readData(data), key=lambda e: e.__getitem__('average'), reverse=True)
self.selectedList=[]
def readData(self,data):
for item in data:
value=item["price"]/item["weight"]
item.setdefault("average", value)
return data
def pick(self):
for i in range(len(self.dataList)-1):
tempList=[]
totleWeight = self.maxWeight
for j in range(i,len(self.dataList)):
if self.dataList[j]["weight"]<=totleWeight:
tempList.append(self.dataList[j])
totleWeight=totleWeight-self.dataList[j]["weight"]
if tempList!=[]:
if dictsum(tempList,"price")>dictsum(self.selectedList,"price"):
self.selectedList = tempList
elif dictsum(tempList,"price")==dictsum(self.selectedList,"price"):
if dictsum(tempList,"price")<dictsum(self.selectedList,"price"):
self.selectedList = tempList
tempList = []
return self.selectedList,dictsum(self.selectedList,"weight"),dictsum(self.selectedList,"price")
class Genetic():
def __init__(self):
pass
if __name__ == "__main__":
# 贪婪算法求解01背包问题
data = [
{"weight": 4, "price": 4},
{"weight": 2, "price": 1.9},
{"weight": 3, "price": 2.9},
]
maxWeight = 5
selected, subweight, subprice = Greedy(data, maxWeight).pick()
result = json.dumps([{'被选项目': selected, '总重量': subweight, '总价值': subprice}])
推荐阅读
-
用回溯法解决0-1背包问题的实战算法与完整代码示例
-
数据结构:数据结构:高效解决连接性问题的连接集详解与 Python 实现 -5.连接集的优缺点
-
pybind11 使用问题 01_使用指定的虚拟环境-2 解决方案 2.1 在 cmake 中设置 python 的路径。
-
用 Python 实现鸡兔同笼问题的新解决方案
-
解决八进制问题的 Astar 算法 Python 实现(图形用户界面)
-
包婷婷 (201550484)作业一 统计软件简介与数据操作-SPSS(Statistical Product and Service Solutions),"统计产品与服务解决方案"软件。最初软件全称为"(SolutionsStatistical Package for the Social Sciences),但是随着SPSS产品服务领域的扩大和服务深度的增加,SPSS公司已于2000年正式将英文全称更改为"统计产品与服务解决方案",标志着SPSS的战略方向正在做出重大调整。为IBM公司推出的一系列用于统计学分析运算、数据挖掘、预测分析和决策支持任务的软件产品及相关服务的总称SPSS,有Windows和Mac OS X等版本。 1984年SPSS总部首先推出了世界上第一个统计分析软件微机版本SPSS/PC+,开创了SPSS微机系列产品的开发方向,极大地扩充了它的应用范围,并使其能很快地应用于自然科学、技术科学、社会科学的各个领域。世界上许多有影响的报刊杂志纷纷就SPSS的自动统计绘图、数据的深入分析、使用方便、功能齐全等方面给予了高度的评价。 R统计软件介绍 R是一套完整的数据处理、计算和制图软件系统。其功能包括:数据存储和处理系统;数组运算工具(其向量、矩阵运算方面功能尤其强大);完整连贯的统计分析工具;优秀的统计制图功能;简便而强大的编程语言:可操纵数据的输入和输出,可实现分支、循环,用户可自定义功能。 与其说R是一种统计软件,还不如说R是一种数学计算的环境,因为R并不是仅仅提供若干统计程序、使用者只需指定数据库和若干参数便可进行一个统计分析。R的思想是:它可以提供一些集成的统计工具,但更大量的是它提供各种数学计算、统计计算的函数,从而使使用者能灵活机动的进行数据分析,甚至创造出符合需要的新的统计计算方法。 该语言的语法表面上类似 C,但在语义上是函数设计语言(functional programming language)的变种并且和Lisp 以及 APL有很强的兼容性。特别的是,它允许在"语言上计算"(computing on the language)。这使得它可以把表达式作为函数的输入参数,而这种做法对统计模拟和绘图非常有用。 R是一个免费的*软件,它有UNIX、LINUX、MacOS和WINDOWS版本,都是可以免费下载和使用的。在R主页那儿可以下载到R的安装程序、各种外挂程序和文档。在R的安装程序中只包含了8个基础模块,其他外在模块可以通过CRAN获得。 二、R语言 R是用于统计分析、绘图的语言和操作环境。R是属于GNU系统的一个*、免费、源代码开放的软件,它是一个用于统计计算和统计制图的优秀工具。 R作为一种统计分析软件,是集统计分析与图形显示于一体的。它可以运行于UNIX,Windows和Macintosh的操作系统上,而且嵌入了一个非常方便实用的帮助系统,相比于其他统计分析软件,R还有以下特点: 1.R是*软件。这意味着它是完全免费,开放源代码的。可以在它的网站及其镜像中下载任何有关的安装程序、源代码、程序包及其源代码、文档资料。标准的安装文件身自身就带有许多模块和内嵌统计函数,安装好后可以直接实现许多常用的统计功能。[2] 2.R是一种可编程的语言。作为一个开放的统计编程环境,语法通俗易懂,很容易学会和掌握语言的语法。而且学会之后,我们可以编制自己的函数来扩展现有的语言。这也就是为什么它的更新速度比一般统计软件,如,SPSS,SAS等快得多。大多数最新的统计方法和技术都可以在R中直接得到。[2] 3. 所有R的函数和数据集是保存在程序包里面的。只有当一个包被载入时,它的内容才可以被访问。一些常用、基本的程序包已经被收入了标准安装文件中,随着新的统计分析方法的出现,标准安装文件中所包含的程序包也随着版本的更新而不断变化。在另外版安装文件中,已经包含的程序包有:base一R的基础模块、mle一极大似然估计模块、ts一时间序列分析模块、mva一多元统计分析模块、survival一生存分析模块等等.[2] 4.R具有很强的互动性。除了图形输出是在另外的窗口处,它的输入输出窗口都是在同一个窗口进行的,输入语法中如果出现错误会马上在窗口口中得到提示,对以前输入过的命令有记忆功能,可以随时再现、编辑修改以满足用户的需要。输出的图形可以直接保存为JPG,BMP,PNG等图片格式,还可以直接保存为PDF文件。另外,和其他编程语言和数据库之间有很好的接口。[2] 5.如果加入R的帮助邮件列表一,每天都可能会收到几十份关于R的邮件资讯。可以和全球一流的统计计算方面的专家讨论各种问题,可以说是全世界最大、最前沿的统计学家思维的聚集地.[2] R是基于S语言的一个GNU项目,所以也可以当作S语言的一种实现,通常用S语言编写的代码都可以不作修改的在R环境下运行。 R的语法是来自Scheme。R的使用与S-PLUS有很多类似之处,这两种语言有一定的兼容性。S-PLUS的使用手册,只要稍加修改就可作为R的使用手册。所以有人说:R,是S-PLUS的一个“克隆”。 但是请不要忘了:R是免费的(R is free)。R语言源代码托管在github,具体地址可以看参考资料。[3] 。 R语言的下载可以通过CRAN的镜像来查找。 R语言有域名为.cn的下载地址,有六个,其中两个由Datagurn,由 中国科学技术大学提供的。R语言Windows版,其中由两个下载地点是Datagurn和 USTC提供的。 三、stata Stata 是一套提供其使用者数据分析、数据管理以及绘制专业图表的完整及整合性统计软件。它提供许许多多功能,包含线性混合模型、均衡重复反复及多项式普罗比模式。用Stata绘制的统计图形相当精美。 新版本的STATA采用最具亲和力的窗口接口,使用者自行建立程序时,软件能提供具有直接命令式的语法。Stata提供完整的使用手册,包含统计样本建立、解释、模型与语法、文献等超过一万余页的出版品。 除此之外,Stata软件可以透过网络实时更新每天的最新功能,更可以得知世界各地的使用者对于STATA公司提出的问题与解决之道。使用者也可以透过Stata. Journal获得许许多多的相关讯息以及书籍介绍等。另外一个获取庞大资源的管道就是Statalist,它是一个独立的listserver,每月交替提供使用者超过1000个讯息以及50个程序。 四、PYTHON
-
[哈里-霍克算法(NCHHO)的改进]利用混沌和非线性控制参数改进哈里-霍克算法的优化性能,以解决与远程信息处理相关的路由问题(Matlab 代码实现)
-
解决 01 背包问题的贪婪算法的 Python 实现
-
贪婪算法在 Python、JavaScript、Java、C++ 和 C# 中的多种实现及其在硬币变化、分数骑士、活动选择和使用哈夫曼编码的最小生成树问题中的应用实例
-
问题解决思路的贪婪算法、回溯算法和动态编程分析 - 决策方法