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有所限制吧
怎樣改進乙個演算法？
學掌門資料分析 我們會在追求快速創新中 又名 快速成名 經常看到，違反科學方法的原則導致誤導性的創新，即有吸引力的觀點卻沒有經過嚴格的驗證。乙個這樣的場景是，對於乙個給定的任務 提高演算法，產生更好的結果，你可能會有幾個關於潛在的改善想法。人們通常會產生的乙個明顯衝動是盡快公布這些想法，並要求盡快實...
怎麼評價乙個演算法的效率？
大雄 複雜度是衡量效能的主要標準，但也不是唯一標準。主要是要對資料量有乙個相對準確的估算。畫乙個圖，橫座標是資料量，縱座標是時間。複雜度高的斜率高，複雜度低的斜率低，而當複雜度低的係數高時，這兩個演算法的曲線在第一象限一定有乙個交點。那麼到底選擇哪個演算法，在於你的資料量在這個交點的左邊還是右邊。如...
作為乙個演算法小白如何學習演算法？如何在有限的時間內快速提公升自己的演算法能力？
已登出 刷題就要耐得住性子，不要只追求數量。從簡單題目開始，逐漸增加難度。拿到題目先自行思考，如果乙個小時左右沒有思路就看解答，不要硬想，參照解答去思考自己的卡點在哪，是哪部分掌握的不好，結合書籍把知識點補牢。刷題可以按照類目，不同的題目可能是考的乙個知識點的不同方面，有的知識點能夠從多個方面考察，...