algorithm - 什么广告组合最赚钱

Question

我有一个面试问题。我不知道如何解决它。请帮我解决。 问题:假设网站中有一个 3X3 的广告 block 。我们有一个数据库表，由第 3 方供应商填充，其中有大量大小从 1X1 到 3X3 不等的广告。 我们必须推导出一种算法，以在任何给定时间点获取最有利可图的广告组合(即找到适合整个 3X3 block 的广告组合，并且该组合必须是最有利可图的组合。 例如。考虑以下数据，条目作为广告

size price
3X3  3000
1X3  1000
2X3  2500

在上面，虽然有一个尺寸为 3X3 的广告可以完美地放入我们的街区，但使用它可以为我们带来 3000 美元，但如果我们选择使用第 2 行和第 3 行，我们可以轻松地填满我们的街区，并且得到 3500，这比使用 3X3 广告要大。如果有如下图所示的新条目，

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

最佳解决方案是使用行号 4。

Answer 1

可以通过dynamic programming来解决，首先找到最好的 1X1 然后最好的 2X1 来自两个最好的 1X1 或一个 2X1。最好的 2X2 是两个最好的 2X1 或一个 2X2 和...你只保存最好的 xXy block 并继续计算，对于 3X1，然后是 3X2，最后是最好的 3X3。