[C] 0/1背包是没法动态规划的， [复制链接]

__BlueGuy_ __BlueGuy_ 当前离线禁止发言好友博客消息论坛徽章: 35	电梯直达 1楼 [收藏(0)] [报告] 发表于 2015-08-27 13:44 \|只看该作者 \|倒序浏览提示: 作者被禁止或删除内容自动屏蔽
	文库\|博客使用正则表达式与lex实现词法分析器 C语言的MIPS汇编实现（四）SWITCH Requested init /linuxrc failed (error -2). 比较 csv 文件中数据差异 LMD ElPack v2019.7新版亮点：Transparent mode全新升级\|附下载

何必抱怨

白手起家

论坛徽章:: 1

2楼 [报告]

发表于 2015-08-27 14:02 |只看该作者

没时间证明？你能证明出来？
动态规划是什么你知道吗？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

__BlueGuy_ __BlueGuy_ 当前离线禁止发言好友博客消息论坛徽章: 35	3楼 [报告] 发表于 2015-08-27 14:30 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？

lxyscls

富足长乐

论坛徽章:: 14

4楼 [报告]

发表于 2015-08-27 14:44 |只看该作者

其实我就想看看谁投了票

http://bbs.chinaunix.net/thread-4185980-1-1.html

1、最优子结构
2、重叠子问题

都具备了吧

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

__BlueGuy_ __BlueGuy_ 当前离线禁止发言好友博客消息论坛徽章: 35	5楼 [报告] 发表于 2015-08-27 15:00 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？

lxyscls

富足长乐

论坛徽章:: 14

6楼 [报告]

发表于 2015-08-27 16:25 |只看该作者

本帖最后由 lxyscls 于 2015-08-27 16:25 编辑

回复 5# __BlueGuy_

这还不好解决？如果递归期间出现对应值已被求出并缓存的情况，不就是重叠子问题？当然我这是反证

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

何必抱怨

白手起家

论坛徽章:: 1

7楼 [报告]

发表于 2015-08-27 16:46 |只看该作者

无语，只以为是的人。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

__BlueGuy_ __BlueGuy_ 当前离线禁止发言好友博客消息论坛徽章: 35	8楼 [报告] 发表于 2015-08-27 16:53 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？

lxyscls

富足长乐

论坛徽章:: 14

9楼 [报告]

发表于 2015-08-27 21:14 |只看该作者

回复 8# __BlueGuy_

三爷，我之前给你的链接没看么

http://bbs.chinaunix.net/thread-4185980-1-1.html

2楼的链接是一个自底向上的过程，非递归

7楼是用递归实现的，可以用一个1+n * 1+w规模的矩阵把中间结果缓存下来，如果已经缓存了，那么函数直接返回。如果有出现缓存的情况，不就是证明有”重叠子问题”吗？

n是物品数目，w是物品重量，当然这个1+n * 1+w的空间有点浪费，因为w是跳变的，不连续

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

返回列表

Chinaunix › 论坛 › 程序设计 › C/C++ › 0/1背包是没法动态规划的，