我为自己设定了一个“简单”的 C# 编程挑战,以优化容量。我第一次尝试时表现不佳(如下文所述),因此我想看看是否有一个标准化算法可以做到这一点,而不使用人工智能/启发式技术,因为我根本不知道它们。我相信有一种已知的方法可以做到这一点,因为该问题可能适用于常见情况,例如 CPU 和其他资源的负载平衡。
问题是我自己给自己设置的。我有3个容器。
- 容器 1 - 容量 15
- 集装箱 2 - 容量 30
- 容器 3 - 容量 15
容器一开始都是空的,因此容量已满。
我也有20件。由于清单很长,我不会全部列出。但它们很简单,可以像
- 第 1 项 - 金额 3
- 第 2 项 - 金额 8
- 第 3 项 - 金额 1
- 第 4 项 - 金额 1
- 第 5 项 - 金额 5
- 等等 .........
我想要做的是将所有物品装入最少数量的容器中,而不打破限制,即装满容量。
- 容器 1 - 物品 2, 1
- 容器 2 - 项目 3、4、5
- 等等 ..............
我正在寻找解决方案,尽管显然解决方案越有效越好。最终我将使容器和物品自动生成,甚至可能添加更多属性(重量和数量)。我知道即使您随机生成它们,解决方案的数量也是有限的,其想法是找到最好的或接近最佳的才是合理的时间。我最初的尝试是首先定义容器和项目对象,然后将项目随机分配给容器,然后尝试通过在接近容量的容器中查找可用空间并用未满的容器中的项目填充它们来进行优化。但效果并不好。我认为最简单的解决方案是按照金额最大的顺序分配项目,然后使用少量的资金来填补空白。我远离了这个初始值,因为我觉得如果添加更多约束,即数量很高(20),但假设新约束的权重仅为(1),这会有缺点。然后我可能会得到一个装满了数量的容器,但几乎没有重量使用,导致容器变得沉重而无法容纳更多。
虽然我更关注这个问题,而不是我使用的 C# .Net 4.0 语言,所以如果您有想法,请随意使用 LINQ 等框架。
如果我发布了一个我错过的众所周知的解决方案的问题,请随时指出我的问题。但我对您能提出的任何解决方案感兴趣。我期待着阅读答复。
你选择了一个非常艰巨的挑战:
- 背包问题 http://en.wikipedia.org/wiki/Knapsack_problem
这个问题是NP完全 http://en.wikipedia.org/wiki/NP-complete这意味着该问题的唯一已知正确解决方案需要检查所有可能的组合。
您可以尝试贪心近似算法如果您可以采用启发式/近似方法,请在第一个链接中进行描述。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)