我得到了一个问题来解决，乍一看，它似乎是某种广义赋值问题（组合优化问题的一个子集：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编写。
如果我理解正确，那么（忽略"类"约束）这就是切削库存问题。 这是一个NP硬优化问题，通常通过将其表述为ILP然后应用一种称为列生成的特殊ILP求解器技术来解决。 简而言之，ILP 对于每种可能的图案或将大理石块切割成最大子块集的方法都有一个变量，该变量记录了应以该特定模式切割的块的数量。 但是可以有大量可能的模式，其中大多数根本不会在最佳解决方案中使用;列生成允许 ILP 求解器使用一组较小的变量，这些变量保证包含所有非零变量（即实际使用的所有模式）。
维基百科页面上有很多好信息。 特别令人感兴趣的是，如果只有一个初始块大小，那么最小化浪费与最小化使用的母块数量相同，然后问题相当于垃圾箱包装。 这个问题仍然是NP难题，但它是"好"的问题之一：有简单的启发式方法（可证明）非常接近最佳解决方案。 您也许可以将其改编为针对您的问题的启发式方法。
将问题表述为 ILP 的一个很好的功能是，添加与类约束相对应的更多约束应该不难。