问下料问题

EN

如果你的问题是“给我代码”，我担心你没有提供足够的信息来实现一个好的解决方案。如果你读了这个答案的全部内容，你就会明白为什么。

如果你的问题是“给我算法”，我担心你在错误的地方寻找答案。这是一个面向技术的网站，而不是一个面向算法的网站。尽管我们程序员当然理解算法(例如，为什么在循环的每次迭代中都将相同的字符串传递给strlen是低效的，或者为什么冒泡排序除了非常短的列表之外是不好的)，但这里的大多数问题都是“如何使用语言/框架Y使用API？”

回答像这样的复杂算法问题需要某种专业知识(包括但不限于，大量的数学能力)。与我们大多数人相比，operations research领域的人更多地解决了这类问题。这是一个关于这个主题的introductory book。

作为一名试图找到现实世界问题的实际解决方案的工程师，我首先会得到以下问题的答案：

由于你的通用问题是NP-完全的(正如Jitamaro已经说过的)，中等大的问题实例需要使用启发式方法。如果你只打算解决小的问题实例，你也许能够实现一个算法，找到确切的最优，但当然你必须警告你的用户，他们不应该使用你的软件来解决大问题instances.

• Are有什么你可以用来降低问题复杂性的模式?例如，这些项目总是还是几乎总是以特定的大小或数量出现？如果你只需要一个好的答案，那么你就不应该浪费脑力或计算精力去尝试提供一个最优的答案。信息，无论是由人提供的还是由计算机提供的，只有当它是可用的时才有用。您的客户是否愿意为高质量的解决方案买单？与数据库或needed.

• How编程不同，这几乎每个人都可以完成，因为算法是最少的(例如，您很少编写SQL数据库提供查询结果的确切过程)，运筹学确实需要数学和工程技能。如果你不为它们收费，你就是在赔钱。

在我看来，这就像是一维装箱的变体。你可以尝试最佳拟合，然后尝试对表b进行不同的排序。无论如何，在3/2的最优解中不存在解决方案，因为这是一个NP-完全问题。这里有一个很好的教程：http://m.developerfusion.com/article/5540/bin-packing。我用了很多方法来解决我的问题。