dmz*_*rsk 7 algorithm mathematical-optimization
我有一个列表products,其中包含shops销售它的列表.
{
'Book A': [ShopA, ShopB, ShopC],
'Book B': [ShopC, ShopD],
'Movie C': [ShopA, ShopB, ShopD, ShopE],
...
}
(商店之间的价格不同)
每个商店也有运费.这是一个"按订单"运输成本,我的购物车中有多少项无关紧要.商店之间也有所不同.
例如:如果我从ShopA购买"Book A",从ShopC购买"Book B",从ShopA购买"Movie C",结果价格为:Book A price in ShopA+ Book B price in ShopC+ Movie C price in ShopA+ ShopC shipping cost+ShopA shipping cost
如果运费是零或者是基于每个项目并且是常数,那么我将按字段对商品列表进行排序price+shipping并从每个集合中获取第一个结果.
我需要购买所有物品一次,找到最低价格和最终产品.
我不是很擅长优化算法和动态编程,所以我需要一个解决方案或只是向正确的方向点头.
这个问题是NP Hard。
我们将显示出打击集问题的减少。
碰集问题：给定套S1,S2,...,Sn和一批k：选择了设定S的大小k，这样，每Si有一个元素s中S，使得s在Si。[备选定义：每个之间的交叉Si和S不为空。
减少：
给定命中集实例，以(S1,...,Sn,k) 创建此问题的实例的形式：
All books cost nothing. In order to buy from each store you pay 1.
The book i is sold by each store denoted in Si, minimal price for this instance is k.
证明：
碰集- >这个问题：假设有一个极小碰集(S1,...,Sn)的大小k。让此命中集为S。通过从每家商店购买S，我们可以按成本购买所有书籍k，因为这些书籍在[我们的建筑中]不花费任何费用，因此我们购买了所有书籍，并从商店精确地付款k，因此总价为k。
问题->命中集：假设k问题的价格为。然后，从问题的产生出发，由于这些书不花钱，因此我们需要在k不同的商店购买以获得所有书。让这些商店成为S。从问题的构建来看S，(S1,...,Sn)
优质教育
结论：
因此，此问题“不那么容易”达到命中集问题，并且没有针对此问题的已知多项式解决方案，因此-如果需要最佳解决方案，则最佳方案可能是指数级方案，例如回溯 [检查所有可能性，并返回最小的解决方案]。
这么少的物品，我有一个解决方案。它是动态的。
我们将迭代处理每个商店。在每一步中，我们都会存储当前的最佳价格，以此我们可以覆盖所有项目子集。在开始时，infinity除了价格的空子集外，其他所有价格都在0价格中。请注意，所有子集都2^Num_products在计数中，但在您的情况下，它们仅约为1000。
现在，我们如何处理下一个后续的商店：考虑您覆盖该商店的产品的每个可能子集（即商店可以实际提供的子集），而所有其他产品由您已经观察到的商店覆盖，因此提高覆盖每个子集的最低成本。这一步需要花费2^Num_products*2^Num_products=4^Num_products大约100万。您为每家商店这样做，最后，答案是覆盖所有要素的成本。所提出的解决方案的整体复杂度4^Num_products * num_shops约为5000万，这是很好的选择。
请注意，这仍然是指数级的，这并不奇怪。感谢您感谢他对NP的难以置信的证明。
编辑在伪代码中添加算法的进一步说明：
init:
cost[subset] = infi
cost[{}] = 0
for shop in shops
new_prices = costs.dup()
for set : subsets
for covered_set : all_subsets(set)
price = covered_set == {} ? 0 : delivery[shop]
remaining = set
for element : covered_set
if shop do not sale element
break for, choose next covered_set
price += el_price[element]
remaining.remove(element)
price += costs[remaining]
new_prices[set] = min(new_prices[set], price)
costs = new_prices
return costs[all]
请注意，这里我将集合用作索引-这是因为我实际上使用了子集的位掩码表示形式，例如1101是包含第1，第2和第4个元素的子集。因此，所有集合的迭代为for (int i = 0; i < (1 << n); i++)。
还有另外一件事：如果要循环一个子集的所有子集，S实际上可以比迭代初始集合的所有子集并检查该子集是否是的子集更快S。如果S也以位掩码表示，则bit_mask此for循环将完成工作：for(int i = bit_mask; i > 0; i = (i - 1) & bitmask)。使用这种方法，可以将算法的复杂度降低到3^Num_products * num_shops。但是，这有点难以理解，您可能需要手工编写一个示例，以确保我编写的循环实际上循环了S的所有子集。关于复杂性，请相信我。
EDIT2编辑中断条件。我还要详细说明集合remaining及其计算：如前所述，dmzkrsk伪代码提到从集合中删除，但是实际上，remaining = set ^ covered_set在使用位掩码表示子集的情况下，您实际上可以只是进行分配（再次进行位操作）。