仅使用set中的数字查找等于或大于给定目标的总和 [英] Find a sum equal or greater than given target using only numbers from set

问题描述

示例1：

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

Shop selling beer, available packages are 6 and 10 units per package. Customer inputs 26 and algorithm replies 26, because 26 = 10 + 10 + 6.

示例2：

销售香料，可用的包装是0.6,1.5和3.目标值= 5.算法返回值5.1，因为它是最接近目标的最大数量（3,1.5,0.6）。

Selling spices, available packages are 0.6, 1.5 and 3. Target value = 5. Algorithm returns value 5.1, because it is the nearest greater number than target possible to achieve with packages (3, 1.5, 0.6).

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

I need a Java method that will suggest that number.

Simmilar算法在 Bin打包问题，但它不适合我。
我尝试了它，当它返回给我的数字小于目标时，我再次使用增加的目标数量再次运行它。但是当包数很大时效率不高。

Simmilar algorithm is described in Bin packing problem, but it doesn't suit me. I tried it and when it returned me the number smaller than target I was runnig it once again with increased target number. But it is not efficient when number of packages is huge.

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

I need almost the same algorithm, but with the equal or greater nearest number.

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

推荐答案

首先让我们将这个问题简化为整数而不是实数，否则我们将无法获得快速优化算法。例如，让我们将所有数字乘以100，然后将其四舍五入为下一个整数。所以说我们有项目大小 x ₁ ，...，x _n 和目标大小 Y 。我们希望最小化该值

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

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

条件

（1） k _i 是所有 n的非正整数≥i≥1

（2） k ₁ x ₁ + .. 。+ k _n x _n - Y≥0

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

一个简单的算法就是问一系列问题，比如

One simple algorithm for this would be to ask a series of questions like

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

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. etc. with increasing z

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

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.

所以让我们使用< A HREF = http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming 相对= nofollow>伪多项式动态规划方法来解决背包：令 F（I，J）是1如果我们可以使用第一个 i 项目达到总项目大小 j （x ₁ ，...，x _我）。对于所有j，我们有重复

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

我们可以在 O（n * Y）时间和中解决此DP阵列O（Y）空间。结果将是第一个j≥Y， f（n，j）= 1 。

We can solve this DP array in O(n * Y) time and O(Y) space. The result will be the first j ≥ Y with f(n, j) = 1.

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

There are a few technical details that are left as an exercise to the reader:

• 如何在Java中实现此功能


• 如何在需要时重建解决方案。这可以使用DP阵列在 O（n）时间内完成（但是我们需要 O（n * Y）空间来记住整个事物。）

• How to implement this in Java
• How to reconstruct the solution if needed. This can be done in O(n) time using the DP array (but then we need O(n * Y) space to remember the whole thing).

这篇关于仅使用set中的数字查找等于或大于给定目标的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！