algorithm - 从有限值列表中寻找目标值的组合算法

Question

我有一个问题，我有一组有限的值，比如说:

[1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6, 6.5, 7, 7.5, 8, 8.5, 9, 9.5, 10]

我想编写一个算法，在其中我提供一个目标值，并在其中返回两个(数量，值)对的列表，以便遵循以下规则。这些规则按重要性降序排列，未编号的规则是“最好有”，但请注意“必须有”。

1. 量值对所有乘积之和等于目标值
2. 使用一个或两个数量值对
3. 每对整数和列表中的一个值
4. 数量之和被最小化
5. 这两个值彼此相差在 2 以内，使得 (value2 - value1) <= 2

• 最小化 1/2 值的数量
• 使用列表中可能的最低值

我的问题如下:这个问题的参数是否属于任何“经典”或众所周知/研究过的计算机算法？如果调整了一些条件，是否可以使这个问题看起来更像一个“经典”优化问题？

我有兴趣以“蛮力”以外的任何其他方式解决这个问题，但是我对不同的优化问题知之甚少。

编辑

这里有一些例子:

#------Example 1------------
print(find_combination(16.5))
# output = ({'qty':1, value:4.5},
#           {'qty':2, value:6})
# The following is invalid because the sum of qty is
# equivalent but more half values are used
# output = ({'qty':3, value:5.5})
#------Example 2------------
print(find_combination(15))
# output = ({'qty':3, value:5})
# The following is invalid because it uses more half
# values, and the sum of the quantity is not at least
# two less than the above answer
# output = ({'qty':2, value:7.5})
#------Example 3------------
print(find_combination(12))
# output = ({'qty':2, 'value':6})
# The following is invalid because the two values are
# not within two of each other. Also, the number of
# different values was not minimized
# output = ({'qty':1, 'value':2},
            {'qty':1, 'value':10})

Answer 1

这样做有什么好处吗:

largest = largest value in the list
if (target <= largest) {
    search for it in the list, and maybe make a sum of two elements if there's a gap where the target would be
} else {
    n = target / largest
    try larger n with smaller values from the allowed set, to check for an exact match.
    Maybe do something clever with the remainder of target/largest to avoid skip some trial-divisions

}

嗯，如果您没有其他所有限制，例如数量相差在 2 以内，这可能是一个好的开始。

使用列表中的最小值与“保持数量的最小总和”相冲突。因此，我假设您只想寻找与另一个候选解决方案相比不会增加数量总和的较小列表值。

如果目标是列表值之一的精确倍数，您的规则甚至不会说您应该返回一对，但我认为这是一个目标。 (规则只说当目标实际上在集合中时，数量=1)。

我现在要放弃，直到你弄清楚规则到底是什么。