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

Question

示例 1:

商店出售啤酒，可用包装为每包 6 个和 10 个单位。客户输入 26，算法回复 26，因为 26 = 10 + 10 + 6。

示例 2:

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

我需要一个 Java 方法来提示该数字。

Bin packing problem 中描述了类似的算法，但它不适合我。我试过了，当它返回给我的数字小于目标时，我再次运行它并增加了目标数量。但是当包数很大时效率不高。

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

类似问题:Find if a number is a possible sum of two or more numbers in a given set - python .

Answer 1

首先让我们将这个问题简化为整数而不是实数，否则我们无法从中得到快速的最优算法。例如，让我们将所有数字乘以 100，然后将其四舍五入为下一个整数。假设我们有项目尺寸 x₁, ..., x_n 和目标尺寸 Y。我们要最小化这个值

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. 我们能否实现 k₁ x₁ + ... + k_n x_n = Y + 0?
2. 我们能否实现 k₁ x₁ + ... + k_n x_n = Y + 1?
3. 我们能否实现 k₁ x₁ + ... + k_n x_n = Y + z?
4. 等随着 z
的增加

直到我们得到"is"的答案。所有这些问题都是 Knapsack 的实例权重设置等于项目值的问题。好消息是，如果我们能为 z 建立一个上限，我们就可以一次解决所有这些问题。很容易证明存在 z ≤ Y 的解，除非所有的 x_i 都大于 Y，在这种情况下，解决方案就是选择最小的 x_i。

所以让我们使用 pseudopolynomial dynamic programming approach解决背包问题:让 f(i,j) 为 1 iif 我们可以用前 i 个项目达到总项目大小 j (x< sub>1, ..., x_i).我们有复发

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) ...

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

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

• 如何在 Java 中实现
• 如何在需要时重建解决方案。这可以使用 DP 数组在 O(n) 时间内完成(但随后我们需要 O(n * Y) 空间来记住整个事情)。