基于用户输入的组合消除

Question

我被这个特殊的问题困住了。为了说明问题的背景，我正在开发一个移动应用程序，它可以帮助将危险货物装载到卡车上。忽略危险货物的大小和重量。

一些危险货物不能装载到卡车上，除非其中一种货物在特定类型的箱子里。

例如，易燃液体和氧化剂不能放在卡车里，除非其中一种放在特定类型的箱子里。所以你可以在盒子里选择其中的一种。

我的问题是，当我们有这些场景的多个案例时，例如：

• 易燃液体和氧化剂除非放在盒子里，否则不能放在一起。
• 易燃液体和有机过氧化物除非放在盒子里，否则不能放在一起
• 如果不能把湿和有机过氧化物放在一起，除非一个放在盒子里，这是很危险的
• 如果不能把湿和氧化剂放在一起就很危险，除非一个放在盒子里。
• 氧化剂和有机过氧化物除非放在盒子里，否则不能放在一起

如果没有列出货物的组合，那么假设它们可以放在一起。例如，湿法时不存在易燃液体和危险物质的组合。这意味着无论是否在一个盒子里，它们都可以放在一起。上面的组合意味着其中一个必须在一个盒子里。

我需要开发一个算法来决定哪些货物需要放在一个盒子里，以便所有这些组合都能工作。

如果能在这方面提供任何帮助，我们将不胜感激。

Answer 1

解决这个问题的一种方法是把它当作一个图形问题来处理：

这意味着：

"Flammable Liquid" "Oxidizer"  
"Flammable Liquid" "Organic Peroxide"  
"Dangerous When Wet" "Organic Peroxide"  
"Dangerous When Wet" "Oxidizer"  
"Oxidizer" "Organic Peroxide"  

变成这样：

=

这就清楚地表明，至少需要两个盒子：

所有的黑线都与红线交叉。当然，谁想让易燃液体在卡车里晃动？尤其是旁边贴着“湿时危险”的东西。规则可能不要求它，但我会争取额外的盒子。如果你太便宜了，不能把它们都装在箱子里，你可能想把最后一个放在出租车里，免得下雨。

我需要找出一个算法，可以决定哪些货物需要放在一个盒子里，这样所有这些组合都能工作。

还没有测试过这一点，但是如果贪婪的算法是可以的，那么它可能就像让每个项都成为一个集合一样简单。创建一个notTogether()方法，获取其中的两个，并将每个方法放置在另一个方法中。现在，将它们全部转储到按集合长度排序的优先级队列中。

包含包含自己的集合的集合不太支持toString()。可能会使调试更容易将对象映射到字符串，从而为这些东西提供可打印的名称。或者，只需分解并使用它自己的Item并由集合支持的自定义toString()类。无论哪种方式，这都是一个循环图，因此您需要限制toString()的深度，否则它将永远循环。

创建一个box()函数，该函数从队列中弹出具有最长集合的项，并遍历队列的其余部分，从其他项中移除该项。当队列中最长的集合为0时，所有需要装箱的东西都会被装箱。

想想看，与其遍历队列的其余部分，不如访问所有您刚刚装箱的内容集合中的所有内容，然后删除所有刚刚装箱的内容。

优先级队列中的集合如下所示：

Organic Peroxide   (3) Oxidizer, Flammable Liquid, Dangerous When Wet  
Oxidizer           (3) Organic Peroxide, Flammable Liquid, Dangerous When Wet  
Flammable Liquid   (2) Organic Peroxide, Oxidizer  
Dangerous When Wet (2) Organic Peroxide, Oxidizer  

box( pq.pull() )会把有机过氧化物变成盒子

Oxidizer           (2) Flammable Liquid, Dangerous When Wet  
Flammable Liquid   (1) Oxidizer  
Dangerous When Wet (1) Oxidizer  

box( pq.pull() )会把氧化剂装进盒子然后你就完蛋了

Flammable Liquid   (0) 
Dangerous When Wet (0) 

把这两个人留在一起还是很奇怪的。

Answer 2

以下是如何以最佳方式对“不太大”数量的货物进行处理的简短大纲：

• 首先配置满足所有约束的框(但不一定是最优的)。例如，你可以从拥有最多“危险邻居”的善开始，把它放进一个盒子里，然后看看剩下的货物，重复前一步，直到不再有任何开放的限制。
• 现在，让我们说，前一步找到了k个箱子为你的n个货物。接下来，如果k-1框就足够了，您可以试一试。这可以通过生成一定大小集合的所有元素组合的标准组合算法来实现.如果在这些组合中，你找到了一个满足所有约束的组合，将k替换为k-1并重复这一步骤，直到k不能再减少为止。

这应该适用于不太大的n和(更重要的) k的初始值不太大。二项分布系数可以很容易地计算n元素外的k-组合数，因此一旦找到初始开始组合，就可以计算每个步骤所需的最大迭代次数，从而估计出您的最大预期运行时间。

Answer 3

由于可能需要装箱的货物数量似乎非常有限，因此您可能只需列举所有情况，消除无效情况，并选择任何需要最少数量框的情况。

对于装在卡车里的5种危险货物(我想这是一种罕见的情况)，你有32个表条目。对于计算机来说，这并不是一个困难或费时的问题。

好的A，B，C类型A+B和A+C是危险的，B+C不是。你需要5盒装A，2箱B，1盒C。

所有可能的组合，包括所需的框数(如果没有在一个组合中装箱，则为0)和有效性：

A B C valid
0 0 0 no
0 0 1 no
0 2 0 no
0 2 1 yes
5 0 0 yes
5 0 1 yes
5 2 0 yes
5 2 1 yes

把B和C放在盒子里需要最少数量的盒子(3)，所以你选择这个解决方案。