从每一组中最多选择一个数字，使所选数字的总和等于给定数字

Question

我有这样的问题，我想知道组合优化或运筹学中是否有合适的模型。问题是：我有几组整数，和一个给定的整数

N

。从每组中最多选择 1 个整数，使所选整数之和等于

N

。 如果没有合适的模型，如何有效地将这个问题写成整数规划问题？谢谢！

我尝试了子集和问题，但情况并非如此。

Answer 1

我不知道针对这个问题专门设计的算法。这是一个可能的 ILP 公式：如果选择了集合 j 的第 i 个元素，则 x_{ij} 为 1，否则为 0。参数a_{ij}是整数的值。我们希望最小化所选元素的数量以获得 N。