如何用堆数据结构求解小数背包？

Question

如果我使用利润/权重的值并将build堆应用于这些值，那么我将按照顺序(N)的时间得到一个最大堆，现在混淆的是如何删除--最大值，因为在我删除最大值之后，我将如何知道与堆中存储的节点关联的权重和利润，因为堆只存储与利润/权重相关的值。

因此，要执行进一步的计算，例如减少背包的容量，并将利润值添加到已经获得的利润值，我将如何进行这些计算？

Answer 1

我假设您正在使用“int”类型的数组来构建max-堆。相反，您可以做的是使用‘struct’类型的数组(如果您正在使用C)，如下所示。

struct items {
   int profit_by_weight;
   int weight;
};

使用‘profit_by_weight’的值构建最大堆(如果您是初学者的话有点棘手)，并在从堆访问项时使用权重的值来完成所需的计算。