g*****u 发帖数: 298 | 1 【 以下文字转载自 Computation 讨论区 】
发信人: grasssu (没有昵称), 信区: Computation
标 题: 请问一个基本的minimization problem有没有近似解法?
发信站: BBS 未名空间站 (Tue May 20 04:38:00 2008)
a set of objects (i from 1 to m), each has:
vi: the value of object i;
si: size of object i.
求选取a subset that can minimize the total value, subject to the condition
that total size greater than or equal to B.
请问有没有已知的近似解法?谢谢! |
c*****t 发帖数: 1879 | 2 google 0-1 knapsack problem.
【在 g*****u 的大作中提到】 : 【 以下文字转载自 Computation 讨论区 】 : 发信人: grasssu (没有昵称), 信区: Computation : 标 题: 请问一个基本的minimization problem有没有近似解法? : 发信站: BBS 未名空间站 (Tue May 20 04:38:00 2008) : a set of objects (i from 1 to m), each has: : vi: the value of object i; : si: size of object i. : 求选取a subset that can minimize the total value, subject to the condition : that total size greater than or equal to B. : 请问有没有已知的近似解法?谢谢!
|
w***g 发帖数: 5958 | 3 整数线性规划,研究了好几十年了吧,有近似解法的。最简单的就是当作一般线性规划
解,然后对结果进行舍入。
【在 g*****u 的大作中提到】 : 【 以下文字转载自 Computation 讨论区 】 : 发信人: grasssu (没有昵称), 信区: Computation : 标 题: 请问一个基本的minimization problem有没有近似解法? : 发信站: BBS 未名空间站 (Tue May 20 04:38:00 2008) : a set of objects (i from 1 to m), each has: : vi: the value of object i; : si: size of object i. : 求选取a subset that can minimize the total value, subject to the condition : that total size greater than or equal to B. : 请问有没有已知的近似解法?谢谢!
|
g*****u 发帖数: 298 | 4 我就是从knapsack problem想到这个的。不一样的,knapsack是求最大值,这个求最小
值,knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。
【在 c*****t 的大作中提到】 : google 0-1 knapsack problem.
|
g*****u 发帖数: 298 | 5 你说rounding a fractional solution么?我也相信已经有人解过这个问题了,不过网
上找不到。你能给出个解法和作者么?我需要做个reference。 |
g*****u 发帖数: 298 | 6 我又想了一下,这个问题的optimal fractional solution就是按密度从小到大排队,
然后从头选一直选到满足size>=B的条件。最后一个选的可能是fractional的或者正好
。但是这样怎么round to a p-approximate integer solution呢?同样,用primal-
dual方法也不容易得出结论。
如果你知道,能不能写出具体算法和证明,或者出处?
【在 g*****u 的大作中提到】 : 你说rounding a fractional solution么?我也相信已经有人解过这个问题了,不过网 : 上找不到。你能给出个解法和作者么?我需要做个reference。
|
w***g 发帖数: 5958 | 7 这个我不是很在行。rounding technique也是随便想的,给不出reference。但是你这个
问题其实就是knapsack problem。假设所有物品的重量的总和为A,先解重量小于等于A
-B的
knapsack problem。把knapsack problem的解从所有物品中抛掉,剩下的就是你的问题
的解。
过。
【在 g*****u 的大作中提到】 : 我就是从knapsack problem想到这个的。不一样的,knapsack是求最大值,这个求最小 : 值,knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。
|
c*****t 发帖数: 1879 | 8 In the question:
求选取a subset that can minimize the total value, subject to the condition
that total size greater than or equal to B.
So basically, 0-1 knapsack would be finding the largest total size
for a given total value. If this size is greater than B, we are done.
过。
【在 g*****u 的大作中提到】 : 我就是从knapsack problem想到这个的。不一样的,knapsack是求最大值,这个求最小 : 值,knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。
|
g*****u 发帖数: 298 | 9 谢谢,和我以前想的一样。不过你有没有觉得,你说的这个knapsack problem的近似解
,比如它的approximation ration是2,但是,原来问题的解其实并没有bounded.
我已经想出一个算法了,不过不是常数级bounded。不过还是谢谢大家!
这个
于A
【在 w***g 的大作中提到】 : 这个我不是很在行。rounding technique也是随便想的,给不出reference。但是你这个 : 问题其实就是knapsack problem。假设所有物品的重量的总和为A,先解重量小于等于A : -B的 : knapsack problem。把knapsack problem的解从所有物品中抛掉,剩下的就是你的问题 : 的解。 : : 过。
|