algorithm - 计算最便宜的购物篮

给出一个产品表：

Products
ID | Name | PriceCents

以及bundles这是一系列产品，在一起购买时会给折扣：

Bundles
ID | Name

BundleItem
BundleID | ItemID | QuantityRequired | DiscountPercent

如果您的basket中有一组商品id和数量，您如何计算哪些捆绑包能为客户提供最优惠的价格？
我想唯一的办法就是用蛮力把所有的组合起来，但是看起来不太优雅。
由于捆绑可以是用户生成的，可以有很多，并且可以存在两个相同的条目，但有不同的折扣。

最佳答案

您可以使用dynamical programming来解决它。
其主要思想是用二进制表示bucket-varialbebinBucket。因此，如果第i位设置为1，则表示您的桶包含第i个乘积，反之亦然。
然后你有一些数组，其中A是集合的最佳价格，它包括当前bucket的二进制表示所描述的所有产品。
一开始，你有A[binBucket]作为一个空桶的价格是binBucket。
然后，迭代一个bucket的所有可能的二进制表示（2N个状态/不同的bucket），并尝试添加所有可能的bucket当您尝试添加bundle时，您的二进制表示将发生变化（作为价格）。
所以，你要更新
A[0]=0
0这里是bundle的二进制表示，与bucket相同。
所以，在最后你会得到你在2n-1位置的阵列中的最佳价格
总效率为O（2N M），其中A[binBucketCurrent + binBundle] = min(A[binBucketCurrent + binBundle], A[binBucketCurrent] + bundle.price)是可用的束数，binBundle是产品数。
更新：当然，可能有很多产品，你不能将它们作为二进制掩码放入变量中因此，您可以使用M，但这会稍微影响效率，然而，这是更直观的方法。