作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-交大98-资讯联招-DS&algo核对
时间Tue Feb 2 09:39:33 2010
※ 引述《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
1F：→ taitin:问一下第七..app 不是取 2吗？ max(opt/app,app/opt)? 02/02 23:37
2F：→ FRAXIS:Ratio是2没错 02/03 09:49
3F：→ FRAXIS:所以我说至少找到0.5Opt的值也对 就看你怎麽写.. 02/03 09:49
修正6-5的答案..
※ 编辑: FRAXIS 来自: 140.119.162.50 (02/14 09:59)