找出数组中元素的任何组合是否与特定大小相加

Question

我试图找出数组中元素的任何组合是否与特定大小相加.

例如输入:{尺寸:[1,1,3,5],目标:2}输出:是/否=>在这种情况下是,因为1 + 1 = 2

我能想到的其中一个解决方案更多的是强力解决方案,我将有n ^ 2次尝试找到特定于目标的大小.

即是这样的:

for(i=0; i< array.size(); i++) {
    for(j=i+1; j< array.size(); j++) {
        if(i+j == goal) {
           return true;
        }
    }
}

这是唯一的方法吗？还有,我的代码是否正确相同？

通过'组合',我不是指'对'(必须恰好是两个项目),而是一个实际的组合(它可以是从0到所有项目的任何地方)

Answer 1

这是背包问题的稍微严格的版本。简而言之，没有“最佳”方法来解决它，因为它是一个 NP 完全问题。

如果有人找到了解决这个问题的最佳方法，我鼓励你立即写一篇论文，提交给 ACM 和 IEEE，并享受你新发现的财富和名声。

我对这类问题没有任何实际经验，但我在大学时确实尝试过遗传算法，它在这类问题上相当成功。就我个人而言，我会尝试一下。

如果您处理的数据集与问题中的数据集一样小，那么您最好只是暴力破解。对于一组 5 个数字，最多有 325 种可能的排列，迭代不会花费太长时间。如果您像 Neuronaut 在评论中建议的那样进行常识性优化，那么时间会更少。

结果是您有一个相关的 XKCD。享受。