问在不同的商店寻找最便宜的购买方式，但商店只收取一次费用。

EN

这个问题有一个非常简单的3-SAT，所以它很难(为每个变量和每个变量的补码引入一个存储库，每次费用为1，然后将变量或补语所满足的所有子句，以及仅在变量和补码存储中出售的每个变量的一个特殊项目，全部成本为0，看看您是否可以以k价格购买所有的东西)。因此，在算法的意义上，没有一种“更好的方法”，它可以保证产生比蛮力搜索更复杂的最优结果。

我认为模拟退火在这里会很好:在每一个退火步骤中，要么添加一个存储，要么删除一个存储，然后找到该商店选择的最低成本。

您可以将其建模为整数线性规划。

常量：P[i][j]是j商店的商品价格，F[j]是进入商店j的费用，W[i]是你需要购买的商品i的数量。设K是一个大常数(比max_{i}(W[i])大)。

变量：N[i][j]将是从j商店购买的商品i的数量。如果您从C[j]商店j购买任何东西，则为1，否则为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]。也就是说，购买物品的数量之和是您最初想要的，如果某些C[j]*K >= N[i][j]的N[i][j]为非零，则N[i][j]条件将强制N[i][j]为非零。

所有变量必须是正的和积分的。

请注意，目标函数(即，您试图最小化的东西)和“受约束”段落中的每个条件在问题的变量中都是线性的。

这立即为您提供了解决问题的方法:将其插入ILP解决程序，例如GLPK。有大量的关于近似和启发式的理论结果来解决这些问题，你可以应用。例如，你可以试着把它作为一个线性规划来解决(也就是说，放松这个问题，使数量可以是实值而不是积分)，然后选择最近的可行整数值解。