寻找最便宜的方式来购买不同的商店的物品，但店有一次费用

Question

所以我有以下问题：

有k商店和n项目。每家商店都可以以不同的价格购买这些商品（并且商店没有全部商品）。但是如果你想在特定的商店购买，你必须支付一次性费用，这对每家商店都是不同的。如何找到最便宜的方式来购买所有物品？

我现在唯一的解决方案是尝试每个可能的商店组合，并寻找最便宜的。有更好的方法还是一些启发式近似？

Answer 1

这个问题有一个简单的3-SAT减少，所以它是NP-hard（为每个变量引入一个商店，并为每个变量补充一次费用1，然后将其作为存储变量或补充所满足的所有条款，以及仅在变量和补充商店中销售的每个变量的特殊项目，所有成本为0，并查看是否可以购买价格为k的所有东西）。因此，从算法的角度来看，这不会是一种“更好的方式”，它可以保证以比蛮力搜索更好的复杂性产生最佳结果。

我认为模拟退火可以在这里很好地工作：在每个退火步骤中，添加或移除商店，然后找到该商店选择的最低成本。

Answer 2

您可以将其设置为integer linear program。

常量： 让P[i][j]是项目i的价格在店j，让F[j]是进入商店j中的费用，并让W[i]是你需要购买物品i的数量。令K为大常数（大于max_{i}(W[i])）。

变量： N[i][j]将从商店j购买的项目数i。 C[j]将从1购买任何商店j，否则0.

然后，你想最小化：sum_{i,j}(P[i][j]*N[i][j]) + sum_{j}(F[j]*C[j])。也就是说，您希望将购买数量的价格乘以产品价格加上您输入的商店的商店费用。

主题为：对于所有i，sum_{j}(N[i][j]) = W[i]，并为所有i和j，C[j]*K >= N[i][j]。也就是说，购买的物品数量的总和就是您最初想要的数量，如果N[i][j]对于某些i非零，则C[j]*K >= N[i][j]条件力C[j]为非零。

所有变量必须是正数和整数。

请注意，目标函数（即，您试图最小化的东西）以及“subject to”段落中的每个条件在问题的变量中都是线性的。

这立即为您提供解决问题的方法：将其插入ILP解算器，例如GLPK。关于近似值和启发式算法的理论结果有很多可以用来解决这些问题。例如，您可以尝试将其解释为一个线性程序（也就是说，放松问题以使量可以是实值而不是整数），然后选择最接近的可行整数值解。