Re: [理工] [資結]-交大98-資訊聯招-DS&algo核對
※ 引述《taitin (小南)》之銘言：
6.
1. x1 = 1, if w1 <= W
x1 = W/w1, otherwise
2. c[i,w] = Max( c[i-1, w], c[i-1, w-wi] + vi )
3. KNAPSACKDEC(vi, wi, W, B)
return KNAPSACKOPT(vi, wi, W) >= B
4. KNAPSACKOPT(vi, wi, W)
這邊應該是要binary search..
5. P, 因為maximum flow min cut
co-P 原因同上
NP, 因為NP包含P
co-NP, 因為co-NP包含co-P
6. O(|E|^2 + |E||V|)
7. 0.5
8. 應該就是Optimal解..
amortized的部分之前好像有人解過了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
→
02/02 23:37, , 1F
02/02 23:37, 1F
→
02/03 09:49, , 2F
02/03 09:49, 2F
→
02/03 09:49, , 3F
02/03 09:49, 3F
修正6-5的答案..
※ 編輯: FRAXIS 來自: 140.119.162.50 (02/14 09:59)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 2 之 9 篇)：