1樓：
首先 @陳碩 的回答是錯誤的，他基於乙個假設：如果答案存在，則存在乙個滿足條件的答案只需要交換兩件物品和。然而這個假設並不成立，反例如下：
A對自己兩件物品估價是,B對A兩件物品估價. B對自己一件物品估價是6，A對B的一件物品估價是4。易得雙方必須交換各自手裡全部商品才能滿意。
結論： 該問題是NP完全問題。
證明如下：
首先他是個NP問題，給出乙個答案（子集M和N）可以很容易判斷它們是否滿足條件。
其次要證明他是NP-Hard的。我們可以構造乙個從判定性0-1揹包問題到它的多項式規約。
判定性0-1揹包問題（NP完全問題之一）：有個物品，每個物品有價值 0" eeimg="1"/>和重量 0" eeimg="1"/>，是否存在乙個子集使得總重量低於：並且總價值大於：
K" eeimg="1"/>。
多項式規約很簡單：對於判定性0-1揹包問題的一組輸入，讓A有乙個物品，A對的估價是，B對的估價是，B有個物品，A對的估價是，B對的估價是。
易得存在乙個符合條件的交易當且僅當存在B中n個物品的乙個子集使得A對其的估價超過A對的估價，並且B對其的估價低於B對的估價。既原判定性0-1揹包問題有解。得證。
2樓：陳芳英
應該是。。給每個物品兩個屬性a和b，對於集合m裡的每個物品，a等於-A給它的估值，b等於B給它的估值。對於集合n裡的每個物品，a等於A給它的估值，b等於-B給它的估值，則這個問題等價於在乙個有ab兩屬性的集合中找乙個子集滿足兩個屬性的和都分別大於0。
揹包問題可以轉變為這個問題（然而我想到的轉化方法貌似不能說是多項式時間，因為要對最大價值做乙個二分）。具體證明不會。。
3樓：陳碩
根據題意，只要
1. A有一件東西x，B有一件東西y
2. A對x的估價低於A對y的估價，B對y的估價低於B對x的估價。
那麼 A 和 B 就可以交換 x/y，交易完成。
這最多只用 O(N^2) 時間就能找到 x/y ，其中 N=m+n，或者找不到。顯然不是 NP 完全。
請問物生政組合是乙個好的組合嗎
Char 還可以吧。我21年高考的，說說我的看法。物理就算學的不好，看你們那物理組和歷史組的分數線 我們是物理開局先贏50分，雖然我選的歷史 狠狠地後悔了 生物，本人認為挺好學的。政治，我就後悔沒選政治。除非你化學學得很好top級別，一般政治賦分都會比化學高。地理我就不說了，反正我學不會。 知乎使用...
如何用乙個很簡單的問題考驗乙個人的中學物理水平？
某科的數學課代表 我們有兩顆人造衛星，視地球為均勻球體，判斷 有一種可能，兩顆衛星沿兩個不同的固定經度執行。有一種可能，一顆衛星沿某一經度執行，另一顆衛星沿著某一緯度執行。在2.的前提下，若兩顆衛星同高度，總存在兩個時間點，使得兩衛星的連線過地心。有一種可能，兩顆衛星沿著不同的固定緯度執行。同步衛星...
如何向乙個普通人說明什麼是物聯網？
孫小星 家裡的冰箱，電視洗衣機，都可以通過網路或者藍芽連線，並接收指令做出一些操作，比如定時洗衣服，定時開空調。多個終端都可以互相通訊，這就是物聯網。其實就是物品可以接入網路連線。 開啟手機，你能在外邊管理你家所有聯網的電氣產品。空調遠端開，窗簾遠處關。最最好的就是冬天你不想起床關燈，有了物聯網，躺...