请教一个算法的问题一个junior问我一个算法的问题，可是我的算法是用英文学的，看不懂他的题干。哪位曾经用中文学过算法的朋友帮个忙吧。谢谢~~
请考虑装箱问题的贪婪算法，他也被称为优先容纳算法（first-fit,FF）：按照每个物
品给出的顺序，把它装入第一个能够容纳它的箱子；如果这样的箱子不存在，就把该物
品放在一个新箱子里，并将该箱子房子箱子列表的尾部。
1）证明FF算法是一个2近似的算法
装箱问题还有一个降序优先容纳算法（first-fit decreasing,FFD）：它在开始的时候
，对物品按照体积的降序进行排序，然后再执行有限容纳算法。
2）这是个几近似算法？证明之。
题目来源：
（美）Anany Levitin
Introdution to The Design and Analysis of Algorithms [noah (2-27 19:01, Long long ago)]
[ 传统版 |
sForum ][登录后回复]1楼
先问一个问题：这个是不是类似于我们常见的背包问题。
就是说，小偷偷东西，发现有N件，第I件价值Vi元，重Wi千克。都是证书。那么他希望带走越值钱的东西。但是背包里面只能容纳W千克。
怎么办呢？
是不是这种问题？因为我印象我们当时用贪心算法。[奕丫 (2-27 21:32, Long long ago)]
[ 传统版 |
sForum ][登录后回复]2楼
装箱问题 ? 有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
[样例]
输入：
24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 接下来n行，分别表示这n个物品的各自体积。
3
12
7
9
7
输出：
0 一个整数，表示箱子剩余空间。[奕丫 (2-27 21:40, Long long ago)]
[ 传统版 |
sForum ][登录后回复]3楼
(引用 奕丫:装箱问题 ? 有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，�...)传说中用动态规划...晕了，两年没看过了[奕丫 (2-27 21:41, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼
approximation algorithmThis bin-pack problem is extensively used as an example for approximation algorithms in NP-complete problems. You should be able to find the explainations and proofs (for both FF and FFD) in a reasonable college computer algorithm textbook, under NP-complete section, but it might not be covered in an undergraduate algorithm course.
Briefly put, given an optimal solution of value O to an NP problem, and an approximation algorithm (in polynomial time) that outputs a solution that is k*O on average, then this approximation algorithm is called a k-approximation.
If I remember correctly, FFD is an 3/2 approximation algorithm.[马甲甲甲 (2-27 23:18, Long long ago)]
[ 传统版 |
sForum ][登录后回复]5楼
你是请教新生，还是混充新生请教？[Bird (2-28 0:04, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼
(引用 Bird:你是请教新生，还是混充新生请教？)我帮新生请教[noah (2-28 0:21, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼
(引用 Bird:你是请教新生，还是混充新生请教？)本来想打电话问你的，不过明天我有考试，你说你看见了就简单得作答一下子呗[noah (2-28 0:25, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼
(引用 马甲甲甲:approximation algorithmThis bin-pack problem is extensively used as an example for approximation algorithms in NP-complete probl...)谢谢“这么多马甲”同学，呵呵[noah (2-28 19:40, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼
(引用 noah:本来想打电话问你的，不过明天我有考试，你说你看见了就简单得作答一下子呗)oh....first fit is 2-approximate...to show that,
We first show that all bins (最多1个例外) at the end will be at least half full
Say each bin has capacity P
The intuition is that, at each instance in the packing process, if there's already a less-than-half full bin, the next item will either
1. settle in a new empty bin, if it's weight > P/2, or
2. settle in that less-than-half full bin
Either case, # of less-than-half full bins remains at most one....you can continue the proof...
For the second part, I dunno how to attack it...will try if i get more time[Bird (3-3 19:10, Long long ago)]
[ 传统版 |
sForum ][登录后回复]10楼
(引用 奕丫:传说中用动态规划...晕了，两年没看过了)不一样。。。[Bird (3-3 19:14, Long long ago)] [ 传统版 | sForum ][登录后回复]11楼
(引用 Bird:oh....first fit is 2-approximate...to show that, We first show that all bins (最多1个例外) at the end will be at least half full...)呵呵，替新生谢过[noah (3-4 1:40, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼
(引用 noah:呵呵，替新生谢过)我是那位2006届SM3新生谢谢学长。以后有问题还要向你们请教了。
3/2算法如何推导的？[Buniverse (3-8 16:42, Long long ago)]
[ 传统版 |
sForum ][登录后回复]13楼