作者LPH66 (ゆびさきミルクティー)
看板CSSE
标题Re: [问题] 演算法-名词定义
时间Sat Apr 15 19:05:21 2006
※ 引述《fenglih (～ 尘埃 ～)》之铭言：
我不确定我所讲的是不是原本定义...
(本来手边该有本称做ItoA的大书 但书现在被我放在别的地方 @@")
: My Question：
: 1. 什麽是The 0/1 knapsack problem?
现有许多物品, 每一个物品都有其重量和价值,
给定一个背包, 有负重量上限,
若每个物品只可选择拿或不拿(而不能拿一部份)
求在负重量限制下能拿走的物品的最高总价值
(如果能拿一部份的物品则为fractional knapsack 是NP问题
而0/1 knapsack是P)
: 2. Minimal spanning tree?
: →这个问题如果这样解释：a spanning tree with the smallest total weight.
: 不知道行不行?
这样子OK
: 3. 2-D rank finding?
这个我不清楚@@"
能给个例子吗?
: 4. Convex hull?
: →The convex hull of a set of planar points is the smallest convex pllygon
: containing all of the points.
: 这样OK吗?
这样子OK
(没记错的话这是ItoA上的定义)
: 5. Heap sort?
利用Heap这个资料结构的特性来进行排序的演算法
: 6. 平衡树?
一个二元搜寻树
若所有非叶节点的节点 其左右子树的高度至多差1
则称此二元搜寻树为平衡树
(英文为AVL tree)
--
[LPH] Oops, your OOP's a problem? 说:
你现在还是看不到狗?
************* 说:
看得到 只是 他们不会跑 就一直呆呆在那边 一直在起点
[LPH] Oops, your OOP's a problem? 说:
你要按"ㄅㄧㄤˋ"它们才会跑啊@@"
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.240.54
1F：推 ledia:0/1 knapsack 是 NP 的? 04/15 19:15
2F：推 fenglih:回楼上，它是NP complete 04/15 20:05
3F：→ ras46:Fraction knapsack 是 P 吧? 04/15 20:21
4F：推 LPH66:我的印象是fraction比较难 @@ 04/15 20:25
5F：推 hardcover:fraction好像可以用greedy,所以是P 04/15 20:37
6F：→ tkcn:fraction是P 从最贵重的开始放就好噜 0-1才是NP 04/15 20:56
7F：推 LPH66:原来我一直都记错了...囧 04/15 21:14
9F：→ FRAXIS:平衡树跟AVL是等价吗? 04/15 22:08
10F：推 hardcover:树叶只会落在相差一阶的高度就是平衡吧？ 04/15 22:16
11F：推 cplusplus:所有叶高度是H或是H-1就是平衡 AVL tree~RB tree~B tree 04/15 23:08
12F：→ cplusplus:都是平衡树 04/15 23:09
13F：推 ledia:那, 最深会在最浅的两倍以内 算不算平衡呢? :P 04/16 01:47