从最接近目标值的数组中选择值的算法？

Question

我有一个几乎排序的值数组28个元素长.我需要找到总和为算法提供的目标值的一组值(或者如果找不到精确的和,则最接近的总和低于目标值).

我目前有一个简单的算法来完成这项工作,但它并不总能找到最佳匹配.它在理想情况下使用一组特定的值工作,但我需要一个更强大,更准确的解决方案,可以处理更多种类的数据集.

该算法必须用C语言编写,而不是用C++编写,并且用于嵌入式系统,因此请记住这一点.

这是我目前的算法供参考.它从可用的最高值开始迭代.如果当前值小于目标总和,则将该值添加到输出并从目标总和中减去该值.重复此过程直到达到总和或用完值.它假设一个几乎提升的排序列表.

//valuesOut will hold a bitmask of the values to be used (LSB representing array index 0, next bit index 1, etc)

void pickValues(long setTo, long* valuesOut)
{
    signed char i = 27;//last index in array
    long mask = 0x00000001;

    (*valuesOut) = 0x00000000;
    mask = mask<< i;//shift to ith bit
    while(i>=0 && setTo > 0)//while more values needed and available
    {
        if(VALUES_ARRAY[i] <= setTo)
        {
            (*valuesOut)|= mask;//set ith bit
            setTo = setTo - VALUES_ARRAY[i]._dword; //remove from remaining         }
        //decrement and iterate
        mask = mask >> 1;
        i--;
    }
}

还有一些参数:

• 值数组可能会按升序近似排序,但不能强制执行,因此假设没有排序.实际上,也可能存在重复值.

• 数组很可能包含一组不能在其范围内创建每个总和的值.如果无法找到确切的总和,则算法应返回创建下一个最小总和的值.

Answer 1

这个问题被称为子集求和问题,这是背包问题的一个特例.维基百科是一些算法的良好起点.

Answer 2

正如其他人所指出的,这与子集和问题的优化版本相同,即NP-Complete.

由于您提到内存不足并且可能使用近似解(基于您当前的解决方案),因此存在用于求解子集和的优化版本的多项式时间近似算法.

例如,给定e> 0,有一个多项式时间算法,它使用O((n*logt)/ e)空间,(t是目标和,n是数组的大小),它给你一个子集和z不小于最优值的1 /(1 + e)倍.

即,如果最大子集和为y,则算法找到子集和z

z <= y <= (1+e)z

并使用空间O((n*logt)/ e).

这样的算法可以在这里找到:http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf

希望这可以帮助.