3

这是问题所在：

用户有一个包含项目的购物篮，其中每个项目都有一组可用的交付类型，这是从一些定义的整体集合中选择的子集（例如 [“UK 2nd class”、“UK 1st class”、“UK Recorded Delivery”] ，但不要太拘泥于确切的名称）。

在完成结帐过程时，应向用户显示单独或组合交付的选项。

分离很容易 - 显示一个表格，其中每个项目都在自己的行中，并且列集与项目中可用交付类型的并集相匹配。每一行都包含一个单选按钮集，每一列都有一个按钮，该按钮是该项目可用的交付类型。

它结合在一起我不确定如何接近。仅当该组中的所有项目共享可用交付类型的子集时，才能将项目组合到一个组中。具有互斥交付类型的项目永远不能在同一个组中。购物篮可以包含来自多个供应商的物品；在这种情况下，来自不同供应商的产品可能不会组合在一起，即使它们共享一种交付类型。

客户要求计算最少组数，与每种邮资的费用无关。是的，这意味着如果四个项目的单独交付成本为 1+£2+£3+£4（四种不同的交付类型），但所有项目都共享一个成本为 15 英镑的第五个交付类型，那么用户将是为“组合”选项提供了一个更昂贵的组。

这是一个单独/组合选项的 HTML 示例。

使用存储过程从数据库中检索项目的可用交付类型，并具有从类型 ID 和供应商 ID 创建的唯一标识符，因此很容易比较类型之间的相等性。但是，我似乎无法想出一个有效的算法来进行比较和生成组。

我希望在数据结构方面的最终结果是（伪代码）：

Basket { List<Item> Items }
=>
GroupsTable {
    List<SelectableDeliveryType> Columns,
    List<Group { List<Item> }> Rows
}

其中每个都Item包含自己的List<AvailableDeliveryType>，然后可以很容易地用于计算出SelectableDeliveryType将其单选按钮放入的列。

任何想法，指向涵盖此的一般算法概念的指针（例如，我不认为这是一个集合覆盖问题）等。非常感谢。

4

1 回答 1

3

通过减少图形着色，这个问题是 NP-hard 的。给定一个由一组由边连接的节点组成的图，该图中的 k 着色是一种对图中的每个节点进行着色的方法，以便没有两个连接的节点具有相同的颜色。色数问题如下 - 可以为图形着色的最小颜色数是多少？

我们可以将任何 NP-hard 色数问题的实例简化为您的问题，如下所示：为每个节点创建一个新产品。对于每条边，标记这两个产品不能被分组到同一个集群中。然后，这些产品的任何聚类都对应于一种颜色——只需将每个聚类中的所有节点都涂上相同的颜色。因此，以最佳方式解决您的问题等同于解决图形着色，因此（在P ≠ NP的假设下）没有多项式时间算法。

不幸的是，众所周知，图形着色很难近似。对于任何 ε > 0 ，没有已知的多项式时间算法可以在最优常数因子内，甚至在 n 1-ε因子内。我认为你最好使用像Chaitin 算法这样的启发式算法，或者找到以不同的方式思考这个问题。

抱歉，结果为阴性，但希望这会有所帮助！

于 2012-07-10T21:24:52.217 回答