什麼是最賺錢的廣告組合

我有一個面試問題。我不知道如何解決它。請幫我解決。問題：讓我們考慮一個網站中有一個3X3廣告塊。我們有一個數據庫表，由第三方供應商填充，其中有大量廣告，大小從1X1和3X3變化。我們必須推導出一種算法，以在任何給定的時間點獲取最賺錢的廣告組合（即）找到適合整個3X3塊的廣告組合，並且該組合必須是最有利可圖的廣告組合。例如：例如。每件作品爲廣告什麼是最賺錢的廣告組合

size price 
3X3 3000 
1X3 1000 
2X3 2500

在上面考慮下面的數據，雖然有可能適合我們的塊完美，用它會把我們3000塊錢，但如果我們選擇使用行尺寸3X3的廣告＃2和3，我們可以很容易地填充我們的區塊，也可以得到3500比使用3X3廣告更大的區塊。如果出現如下圖所示的新條目，

size price 
3X3 3000 
1X3 1000 
2X3 2500 
3X3 5000

的更優化的解決方案是使用行號4

來源

2014-12-02 Gurunath

這個問題似乎是題外話，因爲它不是關於節目。 – 2014-12-02 14:31:58

我想知道您是否可以按價格/每平方米排列它們，並繼續嘗試從排名的「頂部」直到3x3已滿。有時候你必須退出選定的一個，因爲它不能「適合」。 – 2014-12-02 15:02:48

嗨，你找到解決這個問題的辦法嗎？ – Pavan 2015-01-07 09:28:32

它可以通過dynamic programming來解決，首先找到最好的1X1的話，最好是2X1無論是從兩個最好的1X1或一個2X1。最好2X2是從兩個最好的2X1或一個2X2和...你只保存最好的xXy塊並繼續計算，爲3X1然後3X2然後最後最好是3X3。

來源

2014-12-02 12:45:27 Lrrr

你可以得到解決這裏https://github.com/loganathan-s/lucarative_ad（Ruby編寫的）

來源

2015-01-07 09:35:18 loganathan

你把整個東西放在答案中。這將是一個好主意。 – 2015-01-07 09:49:45

什麼是最賺錢的廣告組合

回答

相關問題