尋找顧客對產品的最佳得分任務

我在困難的採訪最後一輪中得到了這個編程問題。尋找顧客對產品的最佳得分任務

所以這個問題有兩個相同大小的列表。

List<Customer>, List<Products>

有一個函數，它是像如下

int score(Customer, Product)並返回一個得分。

我必須找到所有客戶的產品分配應該是最大的任務。

這似乎是一個NP完全問題，在面試時不太可能通過我解決，特別是在面試後幾天仍然不能解決。現在我只是想知道解決方案。
任何人都可以請幫忙嗎？

來源

2013-10-10 RazorProgrammer

請張貼一些代碼。 – Mauren

我確定這個問題非常困難，但你已經成功地讓它變得更加困難： – BartoszKP

莫倫 - 代碼不重要，如果我們告訴他「這是NP問題」，他顯然可以自己做... – libik

您可以將此模型設置爲要查找最大匹配的加權二分圖。

Wikipedia on Matching具有此答案可能有用的：

在加權二分圖中，每個邊緣具有相關聯的值。 A 最大加權二分配匹配被定義爲匹配中的邊緣值的總和具有最大值的匹配。如果圖形不是完整的二分體，缺少的邊將插入值爲0的。發現這樣的匹配被稱爲賦值問題。它可以通過在增強路徑算法中使用修改的最短路徑搜索來解決。如果使用Bellman-Ford算法，則運行時間變爲O（V^2E），或者可以將邊緣成本移位到具有實現O（V^2log（V）+ VE）運行時間的可能性 Dijkstra算法和斐波那契堆。卓越的匈牙利算法解決了分配問題，它是組合優化算法的一個開始。該算法的原始方法需要O（V^2E）的運行時間，但可以通過優先級隊列改進爲O（V^2 log（V）+ V E）時間。

來源

2013-10-10 22:12:59

-1

這是一個（Java）解決方案，「我必須找到所有客戶的產品分配應該是最大的」。

對於C客戶和P產品，它運行在O（CP）時間。

請注意，由於未提供score（）函數的定義，因此我尚未測試此代碼。

Map<Customer, Product> solve(List<Customer> customers, List<Product> products) 
{ 
    Map<Customer, Product> result = new HashMap<Customer, Product>(); 

    for (Customer customer : customers) 
    { 
     int maxScore = Integer.MIN_VALUE; 
     Product bestProduct = null; 

     for (Product product : products) 
     { 
      int currentScore = score(customer, product); 

      if (currentScore > maxScore) 
      { 
       maxScore = currentScore; 
       bestProduct = product; 
      } 
     } 

     if (bestProduct != null) 
     { 
      result.put(customer, product); 
     } 
    } 

    return result; 
}

來源

2013-10-10 22:40:57 stackoverflowuser2010

這不會進行匹配，所有客戶可能會得到相同的產品。 –

問題出在哪裏禁止所有顧客以同樣的產品結束？ – stackoverflowuser2010

我承認這個問題沒有正確表達，但大多數人似乎將其解釋爲雙方匹配問題。伊莫你解決的問題不能被歸類爲「困難的面試問題」。 –

尋找顧客對產品的最佳得分任務

回答

相關問題