所以我有以下问题：
有k商店和n物品。每个商店都可以以不同的价格购买这些商品（有些商店没有所有商品）。但是如果你想在特定的商店购买，你必须支付一次性费用，每个商店都不一样。如何找到购买所有物品的最便宜方式？
我现在唯一的解决方案是尝试所有可能的商店组合并寻找最便宜的。有没有更好的方法或一些启发式近似？
问问题
445 次
2 回答
3
对这个问题有一个非常简单的 3-SAT 减少，所以它是 NP 难的（为每个变量和每个变量的补码引入一个存储，一次费用为 1，然后将所有子句作为存储的项目）通过变量或补码，以及每个变量的特殊物品，仅在变量和补码商店出售，所有成本为 0，看看你是否可以以价格购买所有东西k）。因此，从算法的意义上说，不会有一种“更好的方法”，它可以保证产生比蛮力搜索更复杂的最优结果。
我认为模拟退火在这里可以很好地工作：在每个退火步骤中添加或删除一个商店，然后找到该商店选择的最低成本。
于 2014-10-19T13:38:47.283 回答
2
您可以将此建模为整数线性程序。
常数：令为商店P[i][j]商品的价格，令为进入商店j的费用，令为您需要购买的商品数量。让是一个大常数（大于）。ijF[j]W[i]iKmax_{i}(W[i])
变量：
N[i][j]将是i您从 store 购买的商品数量j。C[j]如果您从 store 购买任何东西，则为 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]也就是说，购买的物品数量的总和是您最初想要的，并且如果some 为非零，则C[j]*K >= N[i][j]条件强制为非零。C[j]N[i][j]i
所有变量必须是正整数。
请注意，目标函数（即您试图最小化的东西）和“主题”段落中的每个条件在问题的变量中都是线性的。
这立即为您提供了解决问题的方法：将其插入 ILP 求解器，例如GLPK。有大量关于近似和启发式的理论结果可以解决这些问题，您可以应用这些结果。例如，您可以尝试将其求解为线性程序（即，放宽问题以便数量可以是实值而不是整数），然后选择最接近的可行整数值解。
于 2014-10-19T13:45:47.967 回答