所以我有以下问题:
有 k 家商店和 n 件商品。每个商店都可以以不同的价格出售这些商品(有些商店没有所有商品)。但是如果你想在特定的商店购买，你必须支付一次性费用，每个商店都不一样。如何找到购买所有元素的最便宜方式？
我现在唯一的解决办法是尝试所有可能的商店组合并寻找最便宜的。是否有更好的方法或一些启发式近似？
最佳答案
这个问题有一个非常简单的 3-SAT 归约，所以它是 NP-hard(为每个变量和每个变量的补集引入一个存储，一次费用为 1，然后作为存储的项目变量或补码满足的所有子句，以及每个变量的特殊项目，仅在变量和补码商店出售，所有成本为 0，看看您是否可以以价格k).因此，就算法而言，不会有“更好的方法”可以保证产生比蛮力搜索复杂度更高的最佳结果。
我认为模拟退火在这里会很有效:在每个退火步骤中添加或删除商店，然后找到该商店选择的最低成本。
关于algorithm - 寻找在不同商店购买商品的最便宜方式，但商店收取一次性费用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26450760/