問一個演算法？

01-08

已知n個物品，第i個物品的代價是w[i]，要求從中取出m個物品。另外有p對整數u和v和它的值w，如果u和v同時選出，那麼它們將有額外價值w。如何選出m個物品，使價值和最大？

我覺得，作為一個添加了這麼多演算法競賽類標籤的問題，不給數據範圍是在耍流氓哦。

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

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

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

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

具體步驟可以看：如何理解動態規劃？ - 冒泡的回答 - 知乎

當然，如果只是要求近似解，用AI演算法吧

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

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

可以將問題「判斷無向圖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，很可能不存在多項式時間演算法。

不怕死就上遺傳，應該還是能找到不錯的解

顯然這不是一個背包問題啊......這有點像大學的數模題

如果對時間的要求不是那麼苛刻，就爆搜吧，總共c(n，m)種情況，然後一個一個算，這個方法答案一定是正確的。

如果是noip的話，可以用貪心騙點分。未經證明，錯誤演算法，僅供騙分使用。首先建圖，這張圖要加權，即額外價值。然後把每個結點的價值表示出來，bfs找m個結點的最大子圖。

少年，請相信

騙分過樣例，暴力出奇蹟。

你可以去看看背包九講。

————————————————

不好意思，沒仔細看題。退役多年，這東西一天不寫退兩天。上面的答案應該沒有太大幫助。

請自行搜索動態規劃，01背包問題

//回答有誤，不要參考了……2333