时间戳

首页 > 解决方案 > 多项式时间内的实重量背包

runtime - 多项式时间内的实重量背包

问题描述

在讲座中，我们考虑了背包问题：有 n 个具有正权重的物品 w1, 。. . , wn 和值 v1, . . . , vn 和容量为 W 的背包（袋）。该问题的可行解决方案是项目的子集，使得它们的总重量不超过 W。目标是找到最大可能总价值的可行解决方案。对于所有权重都是正整数的情况，我们已经讨论了一种动态规划解决方案，可以在 O(nW) 时间内解决背包问题。

a) 假设所有项目的值不是权重，而是正整数。项目的权重可以是任意正实数。如果所有值都是正整数，请描述一个解决背包问题的动态规划算法。

想法 - 对值进行四舍五入，但这只是一个近似值，对吗？这只有在我们的小数空间有限时才有效......

还有其他方法吗？

我对接下来的问题更加困惑：

b) 你的算法的运行时间是多少？证明你的答案。

c) 背包是卡普的 NP 完全问题之一。两种动态规划解决方案都导致多项式时间算法。为什么这与背包的 NP 完全性不矛盾？

标签： runtimetime-complexityknapsack-problemnp

解决方案

A 部分：由于所有项目的值都是正整数，因此项目不能被破坏，这意味着项目必须作为一个整体或留在后面，这是 0/1 背包问题的一个例子。这个问题缺乏贪婪选择属性，因此无法通过贪婪方法解决。动态规划是必要的。

例如，我们有商品 1（总价值：60 美元，重量：10 磅，价值/重量：6 美元/磅），商品 2（总价值：100 美元，重量：20 磅，价值/重量：5 美元/磅）和商品 3 ：（总价值：120 美元，重量：30 磅，价值/重量：4 美元/磅）。

通过贪婪的方法，您首先获得最有价值的物品。项目 1 + 项目 2 = 160 美元。这不是最佳解决方案，因为如果我们包含第 1 项，其他项可能会被强制退出，并且可能会留下空白空间。必须查看具有第 1 项的解决方案与没有第 1 项的解决方案。这称为重叠子问题。

对于最优解，我们的最后一项 n 要么在最优解 A 中，要么不在最优解 A 中。

  • 如果是：在给定 N-{n} 个项目和 Cs{sub n} 的最大容量的情况下，可以通过找到最优解来找到最优解中的其余对象。
  • 如果不是：在给定 N-{n} 个项目和 C 的最大容量的情况下，可以通过找到最优解来找到最优解中的其余对象。

求最大值(N,C)： - 如果 s{sub n} <= C: max(value(N-{n},C),v{sub n} + value(N-{n},Cs{ sub n})) - 如果 s{sub n} > C: value(N-{n},C)

由于这是很多要尝试的子问题，因此创建一个表，其中 #columns = 背包大小 + 1（即 0...C，C 是背包大小），#rows = 任意顺序的输入。用上面列出的规则填写表格，从 C=0 开始，遍历表格中的每个项目。选择提供最高容量和最高总价值的组合。

B部分：算法的运行时间为O((Cn)^2)。该表是容量 x 项目数。表中的每个元素比较 2 个值（不包括元素 n{sub k} 和包括元素 n{sub k} 的最大值）。

C 部分：0/1 背包是 NP 完全的，并且是背包容量的多项式。这与背包问题的 NP 完全性并不矛盾，因为在许多情况下容量为 O(2^n)。

推荐阅读