1

有没有更好的方法来计算笛卡尔积。由于笛卡尔积是一种特殊情况，每种情况都不同。我想，我需要解释我需要实现什么，以及为什么我最终会做笛卡尔积。如果笛卡尔积是我问题的唯一解决方案，请帮助我。如果是这样，如何提高性能？

背景：

我们正在努力帮助客户以更便宜的价格购买产品。

假设客户订购了 5 种产品（prod1、prod2、prod3、prod4、prod5）。

每个订购的产品都由不同的供应商提供。

表示格式 1：

  • 供应商 1 - 提供 prod1、prod2、prod4
  • 供应商 2 - 提供 prod1、prod5
  • 供应商 3 - 提供 prod1、prod2、prod5
  • 供应商 4 - 提供 prod1
  • 供应商 5 - 提供 prod2
  • 供应商 6 - 提供 prod3、prod4

换句话说

表示格式 2：

  • 产品 1 - 由 vendor1、vendor2、vendor3、vendor4 提供
  • 产品 2 - 由 vendor5、vendor3、vendor1 提供
  • 产品 3 - 由供应商提供 6
  • 产品 4 - 由供应商 1、供应商 6 提供
  • 产品 5 - 由供应商 3、供应商 2 提供

现在根据价格选择最好的供应商。我们可以按价格对产品进行分类并取第一个。

在这种情况下，我们选择

  • 来自供应商 1 的产品 1
  • 来自供应商 5 的产品 2
  • 来自供应商 6 的产品 3
  • 来自供应商 1 的产品 4
  • 来自供应商 3 的产品 5

复杂：

由于我们选择了 4 个独特的供应商，我们需要支付 4 个运费。

此外，每个供应商都有一个最低采购订单。如果我们不满足它，那么我们最终也要支付这笔费用。

为了选择产品的最佳组合，我们必须对提供的产品进行笛卡尔积来计算总价格。

total price computation algorithm:

foreach unique vendor 
if (sum (product price offered by specific vendor * quantity) < minimum purchase order limit specified by specific vendor)
totalprice += sum (product price * quantity) + minimum purchase charge + shipping price
else
totalprice += sum (product price * quantity) + shipping price
end foreach

在我们的例子中

  • {vendor1，vendor2，vendor3，vendor4}
  • {供应商1，供应商3，供应商5}
  • {供应商6}
  • {供应商1，供应商6}
  • {供应商2，供应商3}

需要计算 4 * 3 * 1 * 2 * 2 = 48 个组合以找到最佳组合。

  • {vendor1，vendor1，vendor6，vendor1，vendor2} = totalprice1，
  • {vendor1，vendor3，vendor6，vendor1，vendor2} = totalprice2，
    • *
  • {vendor4，vendor5，vendor6，vendor6，vendor3} = totalprice48

现在对计算的总价格进行排序以找到最佳组合。

实际问题：

如果客户订购的产品超过 15 种，并假设每种产品都由 8 个不同的供应商提供，那么我们最终会计算 8^15=35184372088832 组合，这需要几个小时以上的时间。如果客户订购超过 20 种产品，则需要几天以上的时间。

有没有办法从不同的角度解决这个问题？

4

1 回答 1

1

您的问题可能会变得更加复杂。一个简单的例子：

   Product   1     2     3
Vendor 1    10    20    40
Vendor 2    20    10    40
--------------------------
needed cnt 100   100    25

你需要 100 艾尔。P1、P2 的 100 和 P3 的 25。

P1 可以在 V1 中以 1000 美元购买，P2 在 V2 中以 1000 美元购买，P3 在 V1 或 V3 中以 1000 美元购买。

现在运费是免费的，如果您购买 1500，但在其他每个供应商处花费您 200。

因此，如果您在 V1 订购所有商品，您将支付4000：

1000+2000+1000+0 (shipping) = or for the same sum   
2000+1000+1000+0 at V2, or splitted

1000+0+0+200  = 1200 at V1 plus 
0+1000+1000+0 = 2000 at V2,

总计为3200，可以通过您的方法找到。

但是您可以通过这种方式拆分产品 3 的购买：

1000+0+500+0 = 1500 at V1 plus 
0+1000+500+0 = 1500 at V2

总共只有3000并且不会被您的方法找到。

Afaik，在这些主题上有既定的研究，关键词是矩阵和方程组。

您可以将您的问题描述为

f(c11, p11) + f(c22, p12) + f(c13, p13) = c1 => dc1
f(c21, p21) + f(c22, p22) + f(c23, p23) = c2 => dc2
...
f(c31, p31) + f(c32, p32) + f(c13, p33) = c3 => dc3

其中 cij 是供应商 i 处产品 j 的数量，而 pij 是供应商 i 处产品 j 的价格，但 f(c11,p11) 不仅仅是 count*price，而是 count 和 price 的函数，因为可能存在数量折扣。右侧是供应商 i 的采购总额。

这是没有购买折扣的，必须在上面建模。如果运费折扣仅取决于总成本，则可以仅从 ci => dci 建模。

您会尝试最小化总和 (dc1+dc2+...+dcm)。

于 2012-04-26T09:00:22.620 回答