背包具有固定数量的重量

Question

考虑背包问题其中，所有重量都是整数，而且不同权重的数量是固定的。例如，每个项目的重量为1K或2K或4K。每个项目都有一个单位。

问题可以使用动态编程来解决。假设背包容量是 $ c $ ，最有价值的重量 $ w $ 具有一个值 $ v_w $ 。然后，背包的最大值（ $ c $ ）是以下三个值的最大值：

背包（ $ v_1 $ ， $ c-1 $ ），背包（ $ v_2 $ ， $ c-2 $ ），背包（ $ v_4 $ ， $ c-4 $ ）。

是否有更有效的算法？特别是，有没有贪婪的算法？

我尝试了两个贪婪的算法，但它们已经失败了1和2.例如，假设有3个项目，值100,99,51和权重2,1，1,1：

。

• 如果容量为2，那么通过它们的值选择项目的贪婪算法失败（它选择100，而最大值为99 + 51）。
• 如果容量为3，那么通过它们的值/权重比选择项目的贪婪算法失败（它选择99 + 51，而最大值为100 + 99）。

但是，这不排除另一个贪婪算法（通过其他一些标准进行排序）的可能性。有没有贪婪的算法？或者，存在这种算法不存在的证据吗？

Answer 1

在您的情况下，大小只有1,2或4，答案非常简单：

如果背包具有奇数大小，则选择最有价值的大小1项，并将其添加到最后一个插槽。

如果剩余的背包具有两个奇数的尺寸，那么您可以选择最有价值的大小2，或两个最有价值的大小1，以较高的是，将它们放到最后一个狭码2.

现在剩余的背包具有尺寸，这是一个倍数为4.您选择最有价值的大小4，或两个最有价值的大小2，或最有价值的大小1或最有价值的物品尺寸有价值2个加上最有价值的大小1.

与其他尺寸，说大小2,3和5，事情会更加困难。但是，您可以按降序对每个尺寸的项目进行排序，并可以使用动态编程来解决此问题。

我假设时间将是每种固定尺寸的重量的多项式，而多项式取决于权重。但是，您可以在O（n log n）中的降序排序每个重量的项目，如果有m个不同的权重，并且背包的大小是k，则您可以在MW步骤中轻松找到最佳解决方案。

如果权重和k很大，则权重的数量可能小于k。例如，如果k= 10亿和三重重量>= 1亿，则将少于167个可能的总和重量

Answer 2

我的评论没有解决了对不同权重的数量的约束，但由于您还没有约束了不同的值的数量，结果是不同的比率的数量不是约束。这可能是其他种类的贪婪排序的问题。

让我们召唤问题的实例中的不同权重 $ d $ 。

我不知道一种证明 no 其他可能的订购可以工作，但这是一个可以用来排除特定给定的订购的策略。我会为您的贪婪值下降（GVD）算法而努力工作（即使您已经在这种情况下找到了一个反例，所以它没有告诉您任何新的）：

我在评论中描述的贪婪比率 - 降序（grd）算法最佳地解决了0-1 knappsack问题的实例，没有部分项目。这意味着对于一些其他贪婪的命令是正确的，那么就任何这样的GRD可解决问题实例，所有比率都不同，它必须与GRD同意以选择要包括的项目。 （订单不一定是相同的 - 它允许选择以不同的顺序包含的项目。）

让我们从问题的任意实例开始，一些给定的 $ d $ ，它具有不同的比率，太多物品在背包中完全适合，所有项目值至少为3，并且可以通过GRD解决，并寻找将其转换为具有 $ d'= d + 1 $ 不同的实例的方法权重和obeys其他约束（不同的比率，并非所有物品适合所有项目，值 $ \ ge 3 $ ，由grd最佳解），但将混淆gvd。也就是说，我们正在设计一个函数，将实例映射到实例。此函数的域是无限的（例如，采用不同比例的任何实例，并添加重量等于 $ c $ 负重的“关键”项目通过GRD选择的所有项目（即完全“（即，用分数1），并选择项目的值，以使其比率在 $ v_i / w_i $ 和 $ v_ {i + 1} / w_ {i + 1} $ ）;如果我们可以表明该范围也是无限的（例如，因为函数是一对一的），那么我们已经建立了GVD将在使用 $ d'$ 不同的权重。

一个可能的转换是：将所有值乘以 $ 4m $ ，其中 $ m $ 是所有不同权重的产品，并将容量和所有重量乘以2.拍摄由GRD选择的最后一项，其比例 $ 4mv_m / 2w_m $ ，并拆分它几乎注重了一半：一个项目，具有值 $ 2mv_m + 1 $ 和权重 $ w_m $ ，一个value $ 2mv_m-1 $ 和重量也 $ w_m $ 。 （乘以<跨度类=“Math-Container”> $ M $ 确保所有比率都是积分的;略微不同的分子用于保持所有比率，因为所有其他比率是<跨度类=“数学-Container“> $ 0 \ mod 4 $ 。）最后添加一个”诱饵“项目，其中值 $ 4mv_m-3 $ 和权重 $ 2w_m $ 。这种施工在最多的一个新的不同权重，即 $ w_m $ ，所以 $ d'\ le d + 1 $ < / span>。

GRD在这个新实例上产生的（独特的最佳最佳）解决方案将对应于它生成的（独特的最佳）解决方案，它产生于原始实例，选择关键项项目的“一半”并排除诱饵，其中有没有空间。 OTOH，因为我们需要 $ v_i \ ge 3 $ 为输入实例，那么特别是 $ v_m \ ge 3 $ < / span>，暗示 $ 4v_m-3> 2v_m + 1 $ ，因此GVD将考虑在关键项目的一半之前的高度值“诱饵”项目 - 所以那个时候它会选择这个项目如果它有空间，必然会导致次优的解决方案（如果它没有空间，那么它必须是因为它已经采用了GRD未挑选的物品，这也导致了由于我们的假设是最佳解决方案是独一无二的，则次优解。

此实例映射是注射的：不同大小的输入到不同大小的输出，并且对于相同大小的两个不同输入，有一个最小的比率项目出现在两个输入中的一个，并且引导到不显示在另一个输出中的输出项。