PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
Re: [理工] 演算法 0-1knapscak觀念疑問
作者:
a19930301
(-手起刀落o`)
2016-11-18 00:00:44
我認為...背包問題在多項式內 一定 可以解決
但...在這前提是我仍不知道他的時間為何是長那樣
以下有些問題想問一下
看了一下文章都是說O(nW)的W只是個值,我是想成如果W是2000000000..
那麼必然就不是單純一個W可以表示時間
我的疑問是,之所以要這麼多的時間是因為?
(W=重量、V=價值)
(1)最大負重=X,n個物品,n個W,n個V"依序輸入"給電腦然後電腦一步一步
跑DP公式所導致的嗎?
(也就是說,10個物品,第一個輸入,跑一次DP,第二個物品又跑一次DP..依序)
(2)還是因為,要輸入一個物品的參數非單一所導致的?
(因為除了輸入物品個數外,還要輸入物品的重量及價值,還有最大負重)
作者:
w181496
(Kaibro)
2016-11-18 02:05:00
01背包是弱NPC 不是多項式時間可解的個人理解:以電腦2進位角度看 n是物品數 有logn bit 若多t個bit相當物品增加t個(x個物品可x bit表示) 而最大負重W有logW bit 若多t個bit相當於原本值變2^t倍規模一個線性增長 一個指數增長 所以O(nW)才是指數時間
作者: aa06697 (todo se andarà)
2016-11-18 10:47:00
你有辦法找到某個多項式時間解已被證明是NLP問題的話 就推翻NLP目前的所有理論了 可以拿圖靈獎
作者:
FRAXIS
(喔喔)
2016-11-18 11:04:00
NLP是什麼?
作者: aa06697 (todo se andarà)
2016-11-18 11:31:00
剛睡醒打錯了XDD 是NPC
作者:
goldflower
(金色小黃花)
2016-11-18 11:48:00
是論文做NLP 走火入魔嗎XD
作者:
FRAXIS
(喔喔)
2016-11-18 22:48:00
一次給完
繼續閱讀
[理工] 電磁學問題
sunwargod666
[商管]財管,現值相關問題
skyblue15451
Re: [理工] [計組]浮點數102交大
beargg0305
Re: [理工] 遞迴樹問題
ken52011219
[生醫]SNARE complex問題
chunlin01
[理工] 台大102 演算法
ntupumayaya
[理工] 離散 - 費氏數可數
jerry900287
[理工] [線代]正交投影
gy5204301
[理工] 資結 dfs
zoozy
[理工] 線代 100成大電通
yellow60127
Links
booklink
Contact Us: admin [ a t ] ucptt.com