仅使用集合中的数字查找等于或大于给定目标的总和

示例1：

商店里卖啤酒，有6瓶和10瓶的。客户输入 26，算法回复 26，因为 26 = 10 + 10 + 6。

示例2：

销售香料，可用包为 0.6、1.5 和 3。目标值 = 5。算法返回值 5.1，因为它是比包 (3、1.5、0.6) 可能实现的目标最接近的更大数字。

我需要一个 Java 方法来建议该数字。

类似的算法描述于装箱问题，但这不适合我。 我尝试了它，当它返回给我的数字小于目标时，我再次以增加的目标数字运行它。但当包数量很大时，效率不高。

我需要几乎相同的算法，但具有相同或更大的最接近的数字。

类似问题：查找一个数字是否是给定集合中两个或多个数字的可能总和 - python.

First let's reduce this problem to integers rather than real numbers, otherwise we won't get a fast optimal algorithm out of this. For example, let's multiply all numbers by 100 and then just round it to the next integer. So say we have item sizes x₁, ..., x_n and target size Y. We want to minimize the value

k₁ x₁ + ... + k_n x_n - Y

在条件下

(1) k_i is a non-positive integer for all n ≥ i ≥ 1

(2) k₁ x₁ + ... + k_n x_n - Y ≥ 0

一个简单的算法是提出一系列问题，例如

1. Can we achieve k₁ x₁ + ... + k_n x_n = Y + 0?
2. Can we achieve k₁ x₁ + ... + k_n x_n = Y + 1?
3. Can we achieve k₁ x₁ + ... + k_n x_n = Y + z?
4. 等随着增加z

until we get the answer "Yes". All of these problems are instances of the Knapsack problem with the weights set equal to the values of the items. The good news is that we can solve all those at once, if we can establish an upper bound for z. It's easy to show that there is a solution with z ≤ Y, unless all the x_i are larger than Y, in which case the solution is just to pick the smallest x_i.

So let's use the pseudopolynomial dynamic programming approach to solve Knapsack: Let f(i,j) be 1 iif we can reach total item size j with the first i items (x₁, ..., x_i). We have the recurrence

f(0,0) = 1
f(0,j) = 0   for all j > 0
f(i,j) = f(i - 1, j) or f(i - 1, j - x_i) or f(i - 1, j - 2 * x_i) ...

我们可以求解这个 DP 数组O(n * Y)时间和O(Y)空间。结果将是第一j ≥ Y with f(n, j) = 1.

有一些技术细节留给读者作为练习：

• 如何在 Java 中实现这个
• 如果需要，如何重建解决方案。这可以在以下位置完成O(n)使用 DP 数组的时间（但是我们需要O(n * Y)空间来记住整个事情）。