問乙個演算法?

時間 2021-05-08 07:18:18

1樓:栗子

我覺得,作為乙個新增了這麼多演算法競賽類標籤的問題,不給資料範圍是在耍流氓哦。

如果只有20個物品,我完全可以暴力列舉啊233333

2樓:

可以將問題「判斷無向圖G是否有大小為m的clique」規約到此問題:

1. 圖G中的每個頂點對應乙個物品,代價為0。

2. 若點u和點v間有邊,則增加乙個tuple (u, v, 1),表示物品u和物品v同時取可獲得收益1。

則圖G中有大小為m的clique當且僅當構造出的原問題的例項有收益為m * (m - 1) / 2的解。

因此,該問題為NP-hard,很可能不存在多項式時間演算法。

3樓:冒泡

類似01揹包啊,只不過,01揹包在選完前半部分後,考慮後半部分子問題時只考慮剩餘的空間,而這裡需要將和後半段有關的物品(即可產生額外價值的u和v)是否選中也記錄下來,所以狀態不是乙個簡單的W,而是W和有哪些選中的物品的資訊的組合狀態,這個好像是叫複雜條件揹包吧

可以簡單看出,狀態數在最壞情況是和N相關的指數級別的,所以這應該是乙個強NPC問題(其實不是判定問題,應該不屬於NP啦,但可以變個樣子),而01揹包是乙個弱NPC問題

由於記錄狀態是跟前後相關物品的資訊有關,即若u和v有關,則在沒有決策到v的時候,u是否被選中將成為狀態的乙個維度,但如果兩個都已經決策過了,則不需要記錄兩者是否被選過的狀態了,所以先調整N個物品的順序,將相關度高的盡量放一起比較好,這樣可以最大限度壓縮狀態數量

具體步驟可以看:如何理解動態規劃? - 冒泡的回答 - 知乎當然,如果只是要求近似解,用AI演算法吧

4樓:

鑑於題主沒給p的範圍,假設p最大可以到n(n-1)/2。那麼應該是很難找到多項式演算法的,因為可以把邏輯電路問題規約到這個問題,找到多項式演算法就證明了P=NP。

沒有多項式演算法的話,n=10000...畫面太美。所以應該對p或者w有所限制吧

怎樣改進乙個演算法?

學掌門資料分析 我們會在追求快速創新中 又名 快速成名 經常看到,違反科學方法的原則導致誤導性的創新,即有吸引力的觀點卻沒有經過嚴格的驗證。乙個這樣的場景是,對於乙個給定的任務 提高演算法,產生更好的結果,你可能會有幾個關於潛在的改善想法。人們通常會產生的乙個明顯衝動是盡快公布這些想法,並要求盡快實...

怎麼評價乙個演算法的效率?

大雄 複雜度是衡量效能的主要標準,但也不是唯一標準。主要是要對資料量有乙個相對準確的估算。畫乙個圖,橫座標是資料量,縱座標是時間。複雜度高的斜率高,複雜度低的斜率低,而當複雜度低的係數高時,這兩個演算法的曲線在第一象限一定有乙個交點。那麼到底選擇哪個演算法,在於你的資料量在這個交點的左邊還是右邊。如...

作為乙個演算法小白如何學習演算法?如何在有限的時間內快速提公升自己的演算法能力?

已登出 刷題就要耐得住性子,不要只追求數量。從簡單題目開始,逐漸增加難度。拿到題目先自行思考,如果乙個小時左右沒有思路就看解答,不要硬想,參照解答去思考自己的卡點在哪,是哪部分掌握的不好,結合書籍把知識點補牢。刷題可以按照類目,不同的題目可能是考的乙個知識點的不同方面,有的知識點能夠從多個方面考察,...