注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

动态规划——0-1背包问题  

2008-11-06 18:59:12|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
struts2 xml 验证出现 Invalid field value for field 的解决 - 和申 - 和申的个人主页

给定n种物品和一个背包。物品i的重量是wi,体积是bi,其价值为vi,背包的容量为c,容积为d。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对

每种物品只有两个选择:装入或不装入,且不能重复装入。输入数据的第一行分别为:背包的容量c,背包的容积d,物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出为最大的总价值。


我们有以下几点结论:

A)      分支限界法迭代次数与物品单位重量价值数组的取值范围关系紧密。

首先,按照搜索算法的理论知识,我们知道01背包问题是一个子集树问题,在最坏的情形下,我们在给定迭代次数不超过一个限制值(m)的话(在我们的算法中,迭代次数与算法过程中创建的部分子集树的结点数相同),我们所能解决的问题规模为[log(n+1)]-1,事实上,我们在实验中给定m100000,物品个数为n30,在特别情形下(即下面所要说的物品的单位重量价值非常均匀的情形下)迭代溢出的可能很大。

其次,我们的实验结论是物品的单位重量价值越均匀(即分布在一个较小的区间范围内),分支限界法所需的迭代次数越大。而此时的贪心算法所得到的解的相对误差也越小,所以如果不是在严格要求求精确解或给定很小的精度范围内的解的话,不妨使用贪心算法先找一个近似解试试。

   

B)       分支限界法迭代次数跟物品重量与背包容量的比关系紧密。因为物品重量与背包容量的比越小,则背包能装的物品个数就越多,所生成的子集树的深度也就越大,因而在一般情况下(例如在剪枝率差不多的情况下)所需的迭代次数也就越大。

    

C)      分支限界法迭代次数与背包容量占物品总重的百分比关系关系也很紧密,但同时还与其他参数有关,如上面提到的物品重量与背包容量的比等,它们之间的关系十分复杂。我们只能笼统的说,分支限界法迭代次数随着背包容量占物品总重的百分比的增加总体上先升后降。需要指出的,这只是最笼统的估计,事实上情形要复杂的多。

 

D)      分支限界法解决问题的最大实际输入大小的小结。

       在给定迭代次数不超过一个限制值(m)时,最坏的情形下(物品的单位重量价值非常均匀时)只能解决[log(m+1)]-1个实际输入大小的问题。但在物品的单位重量价值的均匀性较为宽松时,我们的程序也能解决较大规模的问题,我们在实验中取m100000时,一般都能以较大可能在这种宽松条件下解决好几百甚至上千的实际输入大小的问题。但在物品的单位重量价值很均匀时,往往连30个物品都难以解决。一般情形下,我们的程序能解决的问题规模大致为50左右,超过100时堆溢出的可能较大。

Failed to convert property value of type [java.lang.String] to required type [double] for property price; nested exception is java.lang.IllegalArgumentException: Cannot convert value of type [java.lang.String] to required type [double] for property price: - 和申 - 和申的个人主页
  评论这张
 
阅读(5035)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016