作者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
推 ledia:0/1 knapsack 是 NP 的? 04/15 19:15
推 fenglih:回樓上，它是NP complete 04/15 20:05
→ ras46:Fraction knapsack 是 P 吧? 04/15 20:21
推 LPH66:我的印象是fraction比較難 @@ 04/15 20:25
推 hardcover:fraction好像可以用greedy,所以是P 04/15 20:37
→ tkcn:fraction是P 從最貴重的開始放就好嚕 0-1才是NP 04/15 20:56
推 LPH66:原來我一直都記錯了...囧 04/15 21:14
→ FRAXIS:平衡樹跟AVL是等價嗎? 04/15 22:08
推 hardcover:樹葉只會落在相差一階的高度就是平衡吧？ 04/15 22:16
推 cplusplus:所有葉高度是H或是H-1就是平衡 AVL tree~RB tree~B tree 04/15 23:08
→ cplusplus:都是平衡樹 04/15 23:09
推 ledia:那, 最深會在最淺的兩倍以內 算不算平衡呢? :P 04/16 01:47