java - 匹配项目值(value)数量以尽可能接近价格点的算法(JAVA)

Question

我不是在寻找答案，因为这是针对他们编码问题的实习面试问题。相反，我正在寻找朝着正确方向前进的线索。

基本上，用户输入 2 个参数。商品数量和价格点。例如，如果用户为商品输入 3，为价格点输入 150 美元，则算法应找到尽可能多的接近价格点 150 的组合。

我认真思考过这个问题，最初的尝试是将价格点除以商品总数。但是这个答案只给了我每个项目的限制范围。

这道题是P NP类型的题吗？

Answer 1

这是 Subset-Sum problem 的变体带有项目数量的附加维度。这个问题是NP-Complete - 所以它没有已知的多项式解，但有一个伪多项式解，假设价格是相对较小的整数。

动态规划比“通常的”子集和问题多了 1 个维度，因为有一个额外的约束 - 您要选择的元素数量。它基本上基于以下递归方法:

基础:

f(0,i,0) = 1 //a combination with the required number of items and the desired price
f(x,0,k) = 0 (x != 0) //no item is left to chose from and the price was not found
f(x,i,-1) = 0 //used more elements than desired

步骤:

f(x,i,k) = f(x,i-1,k)                 +         f(x-price[i],i-1,k-1)
             ^                                           ^
        did not take element i                     used element i

这种方法基本上是蛮力法，在每一步检查所有可能性，但避免对已经解决的较小子问题进行重复计算。

这道题的动态规划解法会在O(n*k*W)中解决其中 n是集合中的项目数，k是您要选择的给定项目数(在您的示例中为 3)和 W是所需的重量/价格。

编辑和澄清:

1. 如果您希望允许多次拾取一个元素，请将步骤更改为:
   f(x,i,k) = f(x,i-1,k) + f(x-price[i],i,k-1) ^ giving a chosen element a chance to be re-chosen
2. 如果您希望允许一些“容差”(允许总和为 W' 的组合，例如 |W-W'| <= CONSTANT ，您可以通过将前两个停止子句更改为以下内容来实现:
   f(x,0,k) = 0 (|x| > CONSTANT) f(x,i,0) = 1 (|x| <= CONSTANT)

另一种解决方案是 O(n^k)这是用 k 生成所有组合元素并检查它们中的每一个。