我有一个问题要解决，乍一看，似乎是某种广义分配问题（组合优化问题的子集：http://en.wikipedia.org/wiki/Generalized_assignment_problem）。
这个问题的描述很不清楚，也不是用英语写的；请耐心听我解释，我尽力解释：
我得到了一组“切割”（任务）要在特定尺寸的大型大理石块上执行目标是完成给定列表中的每个任务，同时最小化大理石丢失量例如，如果我有一个20号的起始块，那么我可以用不同的方式切割它来完成一定数量的任务，同时确保我不会在这个过程中“丢失”大理石。如果我需要3、5、6和6的子块，那么初始大小为20的块就可以了，因为我没有丢失的大理石（3+5+6+6=20）。
因此，我们的目标是完成每一项任务，同时尽可能少地丢失弹珠只要任务全部完成，我可以使用任意数量的起始块。另一个限制是，每个指定长度为l的子块的任务也有一个“类”分配给它，它表示执行此特定切割所需的特定机器。给定一个起始块，我不能使用超过3个不同的类来剪切我的块。我可以在一台机器上做任何我想做的削减，只要我改变类不超过两次。
以下是可以提供给我的数据示例：
2 20 38
7
20
4 1
7 1
3 1
25 1
22 2
22 1
20 2
17 1
10 1
22 2
27 2
26 2
15 3
13 4
12 5
15 6
27 4
27 5
27 7
27 2
第一行给出了可用于执行所有给定任务的不同块的数量，以及每个起始块的大小。
第二行给出了不同“类”切割的总数，表示可以执行所需切割的不同机器的数量。
第三行给出了完成操作所需的总削减量（任务）。在这种情况下，只需执行20个任务即可完成问题。
其余的行给出了所需的剪切以及与此任务相关联的类。
总而言之，我需要使用任意数量的给定起始块执行特定的任务列表，同时尽量减少丢失/不需要的大理石数量。
所以我的问题是：什么是解决这个问题的好方法？我相信贪婪近似算法可能是一个简单而简单的方法来找到一个合理的解决方案，但我真的不确定。
如果问题不清楚，我会事先道歉，如果你需要额外的信息，请随时请求更清楚的指示。
谢谢！
PS：如果有帮助的话，算法将用Java编写。
最佳答案
如果我理解正确，那么（忽略“类”约束）这就是Cutting Stock problem。这是一个NP难优化问题，通常通过将其表示为ILP然后应用一种称为列生成的特殊ILP求解技术来解决简言之，ILP对于每个可能的模式都有一个变量，或者将大理石块切割成一个最大的子块集合，它记录在该特定模式中应该被切割的块的数量。但是，可能有大量的模式，其中大多数模式根本不会在最优解决方案中使用；列生成允许ILP解算器处理较小的变量集，该变量集保证包含所有非零的变量（即实际使用的所有模式）。
维基百科上有很多好的信息特别值得注意的是，如果只有一个初始块大小，那么最小化浪费与最小化所使用的主块的数量是一样的，然后问题等同于Bin Packing。这个问题仍然是np难的，但它是一个“好”的问题：有一些简单的启发式（可证明）非常接近最优解。你也许可以把它改编成一个启发式的方法来解决你的问题。
将问题表示为ilp的一个很好的特性是，添加更多与类约束相对应的约束并不困难。