np-complete

3熱度

4回答

壓縮文件中記錄的壓縮算法是什麼？

假設您有一個由一堆固定大小的塊組成的大文件。每個塊都包含一些可變大小的記錄。每個記錄必須完全適合在一個塊內，然後根據定義這些記錄永遠不會大於完整塊。隨着時間的推移，隨着記錄來自這個「數據庫」，記錄被添加到這些塊並從這些塊中刪除。 在某些情況下，尤其是在將許多記錄添加到數據庫並刪除多個記錄之後 - 許多塊最終只能部分填充。 什麼是一個很好的算法來混洗這個數據庫中的記錄，通過更好地填充部分填充的塊來壓

algorithm language-agnostic np-complete defragmentation knapsack-problem 2008-09-24

---

45熱度

15回答

解決NP完全問題在XKCD

問題問題/漫畫：http://xkcd.com/287/ 我不知道這是做的最好的方式，但這裏是我想出什麼迄今爲止。我使用CFML，但它應該是任何人都可讀的。 <cffunction name="testCombo" returntype="boolean"> <cfargument name="currentCombo" type="string" required="true" />

language-agnostic np-complete 2008-09-26

---

20熱度

2回答

第一個NP完全問題如何顯示爲NP完全？

從對NP完全的維基百科條目： 「最簡單的方法來證明一些新的問題是NP完全是首先要證明它是NP，然後，以減少一些已知的NP完全問題它」 我敢肯定，我明白這一點：如果我有一個問題，我可以證明其是一個NP完全如果我： 表明它是在NP（解決方案到 該問題可以在 多項式時間上驗證 非-deterministic圖靈機）的問題已經知道是NP完全 顯示可以 「降低」新問題 所以，我的問題是，如何是第一NP-完整

computer-science np-complete 2008-11-20

---