多项式时间内的真实重量背包
Real Weights Knapsack in polynomialtime
In the lecture, we have considered the Knapsack problem: There are n items with positive weights
w1, . . . , wn and values v1, . . . , vn and a knapsack (a bag) of capacity W. A feasible solution to the
problem is a subset of the items such that their total weight does not exceed W. The objective is to
find a feasible solution of maximum possible total value.
For the case where all weights are positive integers, we have discussed a dynamic programming solution
that solves the knapsack problem in time O(nW).
a)Assume that instead of the weights, the values of all items are positive integers. The weights of
the items can be arbitrary positive real numbers. Describe a dynamic programming algorithm that
solves the knapsack problem if all values are positive integers.
想法 - 对值进行四舍五入，但这只是一个近似值，对吧？这仅在我们有限小数 space...
时才有效
还有其他方法吗？
我对接下来的问题更加困惑：
b) What is the running time of your algorithm? Justify your answer.
c) Knapsack is one of Karp’s NP-complete problems. Both dynamic programming solutions lead to
polynomial time algorithms. Why is this not a contradiction to the NP-completeness of Knapsack?
A部分：由于所有项目的值都是正整数，因此项目不能被打破意味着项目必须作为一个整体或留下，这是0/1背包问题的一个例子.此问题缺少贪心选择 属性，因此无法通过贪心方法解决。需要动态规划。
例如我们有商品 1（总价值：60 美元，重量：10 磅，value/weight：6 美元/磅），商品 2（总价值：100 美元，重量：20 磅，value/weight ：5 美元/磅）和项目 3：（总价值：120 美元，重量：30 磅，value/weight：4 美元/磅）。
采用贪婪的方法，您会先拿取最有价值的物品。项目 1 + 项目 2 = 160 美元。这不是最佳解决方案，因为如果我们包含第 1 项，其他项目可能会被强制移除，而空的 space 可能会保留下来。必须查看有第 1 项的解决方案与没有第 1 项的解决方案。这称为重叠子问题。
对于最优解，我们的最后一项n要么在最优解A中，要么不在。
- 如果是：给定N-{n}项和C-s{sub n}的最大容量，求最优解即可找到最优解中的其余对象。
- 如果不是：在给定N-{n}项和C的最大容量的情况下，求最优解即可找到最优解中的其余对象
求最大值(N,C)：
- 如果 s{sub n} <= C: max(value(N-{n},C),v{sub n} + value(N-{n},C-s{sub n}))
- 如果 s{sub n} > C: value(N-{n},C)
由于要尝试的子问题很多，因此创建一个 table，其中#columns = 背包大小 + 1（即 0...C，C 是背包大小），#rows = 以任何顺序输入。使用上面列出的规则填写 table，从 C=0 开始，并遍历每个项目的 table。选择提供最高容量和最高总价值的组合。
B部分：算法的运行时间为O((Cn)^2)。 table 是容量 x 项目数。 table中的每个元素比较2个值（不包括元素n{sub k}和包括元素n{sub k}的最大值）。
C 部分：0/1 背包是 NP 完全的，背包容量是多项式的。这与背包问题的 NP 完备性并不矛盾，因为在很多情况下容量为 O(2^n)。
(a) 由于值是整数且权重是实数，我们根据这些值制作 table。更准确地说，让我们修复项目的任意顺序 
。定义 DP(i, v) 是从 1 到 i 的项目子集中的最小权重，其中每个子集的值至少为v。子集的值简单地定义为该子集中所有项目的总和。然后
.
DP(i, v)可以计算所有
和
，问题的最优值由
。在我们填满 table，即计算 DP(v,i) 之后，我们可以扫描并寻找最大 v[=38 的条目=]使得DP(i,v)小于或等于W，即包的容量
(b) 运行 时间为 
，上限为 
(c) 不会与Knapsack 是NP-hard 的事实相矛盾，因为上述算法和你在问题中描述的算法是伪多项式的，即它们取决于 的大小vi 或 wi 不是他们的日志，而是他们的实际大小计算机内存！
In the lecture, we have considered the Knapsack problem: There are n items with positive weights w1, . . . , wn and values v1, . . . , vn and a knapsack (a bag) of capacity W. A feasible solution to the problem is a subset of the items such that their total weight does not exceed W. The objective is to find a feasible solution of maximum possible total value. For the case where all weights are positive integers, we have discussed a dynamic programming solution that solves the knapsack problem in time O(nW).
a)Assume that instead of the weights, the values of all items are positive integers. The weights of the items can be arbitrary positive real numbers. Describe a dynamic programming algorithm that solves the knapsack problem if all values are positive integers.
想法 - 对值进行四舍五入，但这只是一个近似值，对吧？这仅在我们有限小数 space...
时才有效还有其他方法吗？
我对接下来的问题更加困惑：
b) What is the running time of your algorithm? Justify your answer.
c) Knapsack is one of Karp’s NP-complete problems. Both dynamic programming solutions lead to polynomial time algorithms. Why is this not a contradiction to the NP-completeness of Knapsack?
A部分：由于所有项目的值都是正整数，因此项目不能被打破意味着项目必须作为一个整体或留下，这是0/1背包问题的一个例子.此问题缺少贪心选择 属性，因此无法通过贪心方法解决。需要动态规划。
例如我们有商品 1（总价值：60 美元，重量：10 磅，value/weight：6 美元/磅），商品 2（总价值：100 美元，重量：20 磅，value/weight ：5 美元/磅）和项目 3：（总价值：120 美元，重量：30 磅，value/weight：4 美元/磅）。
采用贪婪的方法，您会先拿取最有价值的物品。项目 1 + 项目 2 = 160 美元。这不是最佳解决方案，因为如果我们包含第 1 项，其他项目可能会被强制移除，而空的 space 可能会保留下来。必须查看有第 1 项的解决方案与没有第 1 项的解决方案。这称为重叠子问题。
对于最优解，我们的最后一项n要么在最优解A中，要么不在。
- 如果是：给定N-{n}项和C-s{sub n}的最大容量，求最优解即可找到最优解中的其余对象。
- 如果不是：在给定N-{n}项和C的最大容量的情况下，求最优解即可找到最优解中的其余对象
求最大值(N,C)： - 如果 s{sub n} <= C: max(value(N-{n},C),v{sub n} + value(N-{n},C-s{sub n})) - 如果 s{sub n} > C: value(N-{n},C)
由于要尝试的子问题很多，因此创建一个 table，其中#columns = 背包大小 + 1（即 0...C，C 是背包大小），#rows = 以任何顺序输入。使用上面列出的规则填写 table，从 C=0 开始，并遍历每个项目的 table。选择提供最高容量和最高总价值的组合。
B部分：算法的运行时间为O((Cn)^2)。 table 是容量 x 项目数。 table中的每个元素比较2个值（不包括元素n{sub k}和包括元素n{sub k}的最大值）。
C 部分：0/1 背包是 NP 完全的，背包容量是多项式的。这与背包问题的 NP 完备性并不矛盾，因为在很多情况下容量为 O(2^n)。
(a) 由于值是整数且权重是实数，我们根据这些值制作 table。更准确地说，让我们修复项目的任意顺序 。定义 DP(i, v) 是从 1 到 i 的项目子集中的最小权重，其中每个子集的值至少为v。子集的值简单地定义为该子集中所有项目的总和。然后
.
DP(i, v)可以计算所有和
，问题的最优值由
。在我们填满 table，即计算 DP(v,i) 之后，我们可以扫描并寻找最大 v[=38 的条目=]使得DP(i,v)小于或等于W，即包的容量
(b) 运行 时间为 ，上限为
(c) 不会与Knapsack 是NP-hard 的事实相矛盾，因为上述算法和你在问题中描述的算法是伪多项式的，即它们取决于 的大小vi 或 wi 不是他们的日志，而是他们的实际大小计算机内存！