装箱问题 ? 有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。 [样例] 输入： 24 一个整数，表示箱子容量 6 一个整数，表示有n个物品 8 接下来n行，分别表示这n个物品的各自体积。 3 12 7 9 7 输出： 0 一个整数，表示箱子剩余空间。

你是请教新生，还是混充新生请教？

你是请教新生，还是混充新生请教？

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.

本来想打电话问你的，不过明天我有考试，你说你看见了就简单得作答一下子呗

传说中用动态规划...晕了，两年没看过了

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

呵呵，替新生谢过