知识卡片
装箱问题最小化箱数
装箱问题给出若干大小介于0与1之间的物品,要求装入尽量少的单位容量箱;每箱物品大小之和不得超过1。
目标是箱数,分配方案须逐箱可行。
章末题给出近似性质待证明,不能仅从定义断言算法保证。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第35章 近似算法 · 查看原书依据
You are given a set of n objects, where the size si of the ith object satisfies 0 < si < 1. Your goal is to pack all the objects into the minimum number of unit-size bins. Each bin can hold any subset of the objects whose total size does not exceed 1. a. Prove that the problem of determining the minimum number of bins required is NP-hard. (
参考来源
- 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[50000,55000))。
- 结论依据:第35章加权顶点覆盖、子集和近似方案或章末问题定义与注记;习题未证明的近似比不作已证结论。
- 原始内容:You are given a set of n objects, where the size s i of the i th object satisfies 0 < s i < 1. Your goal is to pack all the objects into the minimum number of unit-size bins. Each bin can hold any subset of the objects whose total size does not exceed 1. a. Prove that the problem of determining the minimum number of bins required is NP-hard. (