学习
实践
活动
专区
工具
TVP
写文章

背包问题-动态规划java实现代码

今天就来分享一篇关于动态规划问题的干货。

01

动态规划的原理

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。

20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划。

1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。

举例:

线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;

区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;

树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;

背包问题:01背包问题,完全背包问题,多重背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;

02

分析与代码实现

分析

题目如下:

在某个深夜里,一个小偷背着一个总共只能装16v体积的背包进入一家商店偷东西:

假如店里有手机一部,价格为2000元,体积为1v;薯片一包,价格为5元,体积为5v;翡翠一块,价格为100000元,体积为10v;一套四大名著,价格30元,体积为6v;电脑一台,价格为6000元,体积为10v。

怎么样能够让背包装的下,并且又能使拿到的东西总价格最多?

这种情况下,一共5件东西。小偷偷东西的事件只有两种:拿,不拿。当他拿的时候,背包体积变小,物件数量减1;

当他不拿的时候,背包体积不变,物件数量减1(因为小偷选择不拿这件东西的时候不会返回继续拿,所以他失去了这件东西选择的机会)。

物件数量为i,背包容纳量为v。

1.不拿 b(i-1,v)

2.拿 b(i-1,v-该物品的体积),两者取最大值

核心代码:

代码分析

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20201218A0ERW700?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券