贪心算法

贪心算法

背包问题

联机算法

存在使用4/3箱子的最优字数的数字

  • 下项适合算法
    不超过2M的箱子
  • 首次适合算法
    17/10 M 的箱子
  • 最佳适应算法
    1.7倍左右

脱机算法

首先排序，然后放入大件物品

  • 首次适合递减算法
  1. 放到外面的物品最多是1/3
  2. 外加箱子的物品的个数最多是M-1
  3. 11M/9+4的上界
  • 最佳适合递减算法
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 基础-10：贪心算法
    概述 在前文中解释了动态规划的基本思想，动态规划通过将一个问题划分为规模更小的有限个子问题进行求解，一般用于求解最...
    CodingTech阅读 7,559评论 0赞 10
  • 可用贪心算法解决的几个基本问题
    可用贪心算法解决的几个基本问题 关键：看问题有没有贪心选择性质和最优子结构性质。有些问题看似是可以用贪心算法，但是...
    碧影江白阅读 11,433评论 1赞 2
  • 贪心算法
    目录 1.贪心算法步骤 2.两个关键要素 3.两种背包问题3.1 0-1背包问题（适用于动态规划，不满足贪心选择性...
    王侦阅读 10,461评论 2赞 3
  • 【算法】贪心算法(0-1背包问题)
    什么是贪心算法？ 贪心算法并不是一个具体的算法，而是一种算法的思想，或者说是解决问题一种思路。这就有两个关键的点，...
    一口咖啡一口茶阅读 14,676评论 10赞 48
  • 2017年9月27日
    2017年9月27日 D48阿尔法号+阿基米德舱+刘虹秀+打卡 今日任务: 收听晨间导读：亲密关系中,沟通重要,行...
    伊秀儿阅读 728评论 0赞 0