一个无序的整型数组有N个数,现在输入一个数,求数组里的数怎么相加能得到这个数,或是跟这个最相近的数
一个无序的整型数组有N个数,现在输入一个数,求数组里的数如何相加能得到这个数,或是跟这个最相近的数
一个无序的整型数组有N个数,现在输入一个数,求数组里的数如何相加能得到这个数,或是跟这个最相近的数!
请算法高手近来看看啊!
------解决方案--------------------
考虑一个含有N个数的集合，他有2^N - 1个非空子集，lz的问题就是在这些子集中找到一个子集，使得子集中元素的和等于指定的一个数，或者最接近这个数。枚举所有子集就可以解决问题，时间复杂度为O(2^N)，当然，通过排序或者其他的某些手段，可以减少需要检测的子集数量，但是由于该问题已经被证明为是一个NP完全的问题，所以在复杂度层面上不会有太多变化。
更多的信息lz可以google“子集和问题”
------解决方案--------------------
1,2,3,4,5,6,7,8,9,10
target = 11
取小于等于11的最大值10.
target= 11 - 10 = 1
取小于等于11的最大值1.
将10排除出数组.
取小于等于11的最大值9.
target= 11 - 9 = 2
取小于等于11的最大值2.
依此类推求出所有组合。
以上仅针对正好等于的情况。
如果是最接近的情况。也可以使用类似方法。保存一个当前最接近的组合。每当搜索到新的更接近的组合，就用它替换当然最接近组合。
------解决方案--------------------
如果是有限个元素的集合，且和式不允许使用重复数字，那么其实就是下面算法
给的集合A，定义集合S={s|s∈A}，也就是说s是A的子集构成的集合
这样，和式和S的元素一一对应，给定一个A，我们就可以计算出所有的和，这样就可以得出答案了
如果不满足本帖的假设，就应该没有解
一个无序的整型数组有N个数,现在输入一个数,求数组里的数如何相加能得到这个数,或是跟这个最相近的数!
请算法高手近来看看啊!
------解决方案--------------------
考虑一个含有N个数的集合，他有2^N - 1个非空子集，lz的问题就是在这些子集中找到一个子集，使得子集中元素的和等于指定的一个数，或者最接近这个数。枚举所有子集就可以解决问题，时间复杂度为O(2^N)，当然，通过排序或者其他的某些手段，可以减少需要检测的子集数量，但是由于该问题已经被证明为是一个NP完全的问题，所以在复杂度层面上不会有太多变化。
更多的信息lz可以google“子集和问题”
------解决方案--------------------
1,2,3,4,5,6,7,8,9,10
target = 11
取小于等于11的最大值10.
target= 11 - 10 = 1
取小于等于11的最大值1.
将10排除出数组.
取小于等于11的最大值9.
target= 11 - 9 = 2
取小于等于11的最大值2.
依此类推求出所有组合。
以上仅针对正好等于的情况。
如果是最接近的情况。也可以使用类似方法。保存一个当前最接近的组合。每当搜索到新的更接近的组合，就用它替换当然最接近组合。
------解决方案--------------------
如果是有限个元素的集合，且和式不允许使用重复数字，那么其实就是下面算法
给的集合A，定义集合S={s|s∈A}，也就是说s是A的子集构成的集合
这样，和式和S的元素一一对应，给定一个A，我们就可以计算出所有的和，这样就可以得出答案了
如果不满足本帖的假设，就应该没有解