1

这是我为我的一个 CS 课设置的问题，我有点卡住了。这是问题的摘要。

Create a program that will:
1) take a list of grocery stores and its available items and prices
2) take a list of required items that you need to buy
3) output a supermarket where you can get all your items with the cheapest price

input: supermarkets.list, [tomato, orange, turnip]
output: supermarket_1

The list looks something like
supermarket_1
$2.00 tomato
$3.00 orange
$4.00 tomato, orange, turnip

supermarket_2
$3.00 tomato
$2.00 orange
$3.00 turnip
$15.00 tomato, orange, turnip

If we want to buy tomato and orange, then the optimal solution would be buying 
from supermarket_1 $4.00. Note that it is possible for an item to be bough 
twice. So if wanted to buy 2 tomatoes, buying from supermarket_1 would be the 
optimal solution.

到目前为止，我已经能够将数据集放入一个数据结构中，希望能让我轻松地对其进行操作。我基本上有一个超市字典，该值将指向另一个字典，其中包含从每个条目到其价格的映射。

supermarket_1 --> [turnip --> $2.00]
                  [orange --> $1.50]

一种方法是使用蛮力，获取所有组合并找到满足解决方案的任何一个并找到最小的那个。到目前为止，这是我能想到的。没有假设两种物品组合的价格会低于单独购买的价格。

欢迎任何建议提示

4

3 回答 3

2

寻找特定超市的最优解是集合覆盖问题的推广，它是 NP 完全的。减少如下：给定一个集合覆盖问题的实例，只需定义一个成本函数，将 1 分配给每个组合，应用解决您的问题的算法，您就可以获得集合覆盖实例的最优解。（因此找到最小价格对应于找到最小覆盖集数量。）因此，您的问题是NP-hard，并且您不能期望找到在多项式时间内运行的解决方案。

你真的应该实现你提到的蛮力方法。作为第一步，我也建议您这样做。如果性能不够，您可以尝试使用 MIP 公式和 CPLEX 之类的求解器，或者您必须开发启发式方法。

对于单个超市来说，找到一个混合整数程序（MIP）是相当简单的。让产品组合包含在解决方案中的频率、成本和产品组合中包含x_i产品的频率为整数。然后，您正在最小化ic_iw_ijji


sum_i x_i * c_i

受条件如


sum_i x_i * w_ij >= r_j,

哪里r_j是需要产品的频率j。

于 2012-04-20T05:32:16.703 回答
1

好吧，你有一个方法，所以现在实现它，这样你就有了可以提交的东西。蛮力解决方案应该不会花很长时间来编写代码，然后您可以获得一些性能数据，您可以更深入地考虑问题。估计大城市合理购物范围内的超市数量。创建这么多超市记录并将它们链接到具有随机价格的产品表（这比解决方案更多工作）。

运行你的蛮力解决方案。它有效吗？如果它输出一个解决方案，“手动”将价格相加，并将它们与随机获取的其他三个“超市”记录（只需选择一个数字）列出，显示总数小于或等于。修改你清单上某件商品的价格，让解决方案不再便宜，重新运行，让你得到不同的解决方案。

是否如此之快以至于没有进一步的工作是合理的？如果是这样，请在报告的结论部分说明，并将批次发布给您的教授/助教。您了解了任务，考虑了它，提出了解决方案，实施了它，使用具有代表性的数据集对其进行了测试，从而证明了功能是可证明的并且性能是足够的 - 您的任务已经结束，去酒吧，考虑下一个一杯啤酒。

于 2012-04-19T08:15:13.757 回答
0

我不确定您所说的“蛮力”解决方案是什么意思。为什么不直接计算每个超市的物品清单的成本，然后选择最小值？复杂性在 O(#items x #supermarkets) 中，这很好。

关于您的数据结构，您也可以简单地拥有一个矩阵（二维数组）price[super][item]，并为您的超市/商品使用 id。

于 2012-04-19T10:32:06.740 回答