問題詳情

37. 電腦演算法中，0/1 Knapsack Problem 面對 n 筆資料時，它的 the worst time complexity是 O( )？
(A) n2
(B) n log n
(C) n3
(D) NP-hard

參考答案

答案：D
難度：困難0.2
統計：A(1),B(7),C(2),D(3),E(0)

用户評論

【Keep Happy Mo】評論

NP 問題的代表問題之一是售貨員旅行問題 (traveling salesman problem)。有一個售貨員要開汽車到 n 個指定的城市去推銷貨物，他必須經過全部的 n 個城。現在他有一個有此 n 城的地圖及各城之間的公路距離，試問他應如何取最短的行程從家中出發再到家中？

【william】評論

Knapsack Problem 背包問題