整数和的算法

Question

可能重复:
找到所有可能的数字组合以达到给定的总和

我必须创建一个方法,从数组中选择数字,其总和将是必需的,或者如果不存在则选择最小的更大的数字.这个函数的算法是什么？

public int[] selectExactSum(int[] X, int SUM) {
}

例如:数字为:{5,2,8,4,6},所需总和为12.

结果将是:{2,4,6}

如果所需的总和为13,则结果为:{2,8,4} - 因此,总和将在这种情况下为14 - 第一个最小的较大的一个.

如果要求总和为15,则可能的结果为:{5,2,8}或{5,4,6}.在这种情况下,返回您选择的一个 - 可能是您获得的第一个.

自定义数字和总和的算法是什么？

谢谢,西蒙

Answer 1

这是称为子集和的问题的一般情况.这是一个NP完全问题,因此最着名的算法是伪多项式.如果您了解上述链接算法,则可以扣除解决问题所需的修改.