美文网首页
2018-11-14

2018-11-14

作者: shiyuqi | 来源:发表于2018-11-14 23:45 被阅读0次

今天学了动态规划一些知识，着重看了一下动态规划之背包算法（主要是0-1算法和部分算法），关于动态规划的问题重点是建立递推关系式，有了递推关系式，问题就好解决了，一般的动态规划问题可以理解为就是一个决策问题，当前决策必须对最终的结果是最优的，下面来说说0-1背包问题：限重R，N个物品，重量和价值分别是wi, vi,怎样选取使得价值最大,当前物品选或不选，取其中较大值,其递推关系式为(f[i][j]表示前i个物品使得重量为j时的最大价值）

f[i][j] = max( f[i-1][j], f[i-1][j-wi] + vi ) 前者表示该物品不拿，后者表示该物品拿，根据递推写循环，其复杂度是m*n

关于部分的背包问题（就是可零碎选取），用vi/wi， 然后排序取即可

关于学长提到的可重复选取问题，三重循环，复杂度n^2，建议再看一下呢  f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

相关文章

网友评论

      本文标题：2018-11-14

      本文链接：https://www.haomeiwen.com/subject/rajsfqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|2018-11-14|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！