1

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

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

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

这个问题是 P NP 类型的问题吗？

4

2 回答 2

2

这是子集和问题的一种变体，具有项目数量的附加维度。这个问题是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并检查它们中的每一个的解决方案。

于 2014-03-04T10:44:40.023 回答
0

该问题与子集和问题相同，可以使用类似于背包问题的 DP 解决方案来解决，但略有不同，因为您可以拥有可能大于价格点的子集。可以使用解决一般子集和问题的智能调整来管理这种变化：-

子集和的 DP 解决方案：-

1. Sum = Price Point.
2. SubSum(Sum,n) = Maximum(SubSum(Sum-Price[n],n),SubSum(Sum,n-1)))
3. SubSum(PricePoint,n) = Maximum Closest Subset Sum to Price Point <= Price Point

以上给出了最接近但小于或等于Price Point的子集总和，但在某些情况下，略大于价格点的子集总和是正确的子集总和，因此您需要评估Subset Sum大于 的值Price Point。您需要评估的该值的上限是所有项目Bound = PricePoint + MinPrice中MinPrice的最低价格。比找到SubSum(x,n)最接近的值PricePoint

于 2014-03-04T11:01:40.073 回答