hi,你好!欢迎访问本站!登录
本站由简数采集腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - PHP教程 - 正文 请牢记本站网址www.sosophp.cn

01背包题目动态计划【php教程】

2019-12-01PHP教程搜搜PHP网49°c
A+ A-

动态计划的基本思想:

动态计划算法一般用于求解具有某种最优性子的题目,即我们寻常所说的最优子构造性子。

动态计划算法与分治法相似,其基本思想也是将待求解题目剖析成多少个子题目,先求解子题目,然后从这些子题目的解获得原题目的解。与分治法最大的区别是,适合于用动态计划求解的题目,经剖析获得子题目每每不是相互自力的,即下一个子阶段的求解是建立在上一个子阶段的解的基础上,举行进一步的求解。

若用分治法来解这类题目,则剖析获得的子题目数量太多,有些子题目被反复盘算了很屡次。假如我们能够保留已处理的子题目的答案,而在须要时再找出已求得的答案,如许就能够防止大批的反复盘算,节省时间。我们能够用一个表来纪录一切已解的子题目的答案。不论该子题目今后是不是被用到,只需它被盘算过,就将其效果填入表中。

题目形貌:

给定N中物品和一个背包。物品i的分量是Wi,其代价位Vi ,背包的容量为C。问应当怎样挑选装入背包的物品,使得转入背包的物品的总代价为最大??

在挑选物品的时刻,对每种物品i只要两种挑选,即装入背包或不装入背包。不能讲物品i装入屡次,也不能只装入物品的一部分。因而,该题目被称为0-1背包题目。

题目剖析:令V(i,j)示意在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大代价,则能够获得以下的动态计划函数:

(1)   V(i,0)=V(0,j)=0 

(2)   (a)  V(i,j)=V(i-1,j)    j<wi  

      (b)  V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) }   j>wi

(1)式表明:假如第i个物品的分量大于背包的容量,则装人前i个物品获得的最大代价和装入前i-1个物品获得的最大价是雷同的,即物品i不能装入背包。

(2)式表明:假如第i个物品的分量小于背包的容量,则会有一下两种状况:(a)假如第i个物品没有装入背包,则背包中物品代价就即是把前i-1个物品装入容量为j的背包中所获得的代价。(b)假如把第i个物品装入背包,则背包物品的代价即是第i-1个物品装入容量位j-wi 的背包中的代价加上第i个物品的代价vi; 明显,取两者中代价最大的作为把前i个物品装入容量为j的背包中的最优解。

引荐教程:PHP教程

以上就是01背包题目动态计划的细致内容,更多请关注ki4网别的相干文章!

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  选择分享方式
  移步手机端
01背包题目动态计划【php教程】

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章