将一个数组划分为最佳的不等于总和子列表

Question

嗨，我试图找到什么样的数据结构算法，我必须在这个问题中使用。我有两个数组，一个包含产品重量，另一个包含成本。我必须将产品重量分成最佳数量的包装，每个包装具有相同的重量，单个产品的成本或总产品的成本在分割后不应超过每个包装300美元。

例：权重= [1000,500,500]成本= [150,75,75]

我们并不需要把它们分为多个包，因为所有产品的总成本不超过$ 300。所以我们可以把它们作为一个包裹发送。

例：权重= 1000，500，500]成本= [200，100，100]

现在的所有产品的成本超过$ 300，所以我们必须把它们分为具有相等的权重包而且每个成本不应该超过300美元。

我们可以把它们分成两个包，一个包含1000克，另一个包含1000克（500 + 500），成本不会超过300美元。

我不是在寻找代码或东西。我只需要一个关于如何分割多个包的东西的提示或算法。

Answer 1

找到具有给定权重的单个子集是NP难的。如果你有某种方法可以识别给定重量的所有子集，并且其成本低于300美元，那么你需要解决一个确切的覆盖问题，这是一般的NP难题。所以你不能指望在最坏的情况下找到任何小于指数复杂度的算法。

但我会尝试在这里是这样的：

let W = total weight of all packages 
let N = total number of packages 
for k = 1, 2, 3, ..., N 
    find all subsets of packages with weight W/k and cost less than $300 
    if there's an exact cover: stop with solution. 

您可以采用动态规划假设不同重量和成本的数权重的子集和成本足够小。您可以使用跳舞链接算法找到确切的封面。