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

Z时代
2024-01-10
分类：问答

我有一个排序的值数组，长度为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--;
    }
}