在讲座中，我们考虑了背包问题：有n个项目的权重为正w1 ，。 。 。 ，wn和值v1，... 。 。 ，vn和容量为W的背包（一个袋子）。问题是这些项目的子集，使它们的总重量不超过W。目标是找到最大可能总价值的可行解决方案。对于所有权重均为正整数的情况，我们讨论了一种动态编程解决方案可以在O（nW）时间内解决背包问题。
a）假设所有项目的值均是正整数，而不是权重。的重量这些项目可以是任意正实数。描述一个动态编程算法如果所有值都是正整数，则可以解决背包问题。
想法-将值取整，但这只是一个近似值吧？仅当有限的十进制空间有限时，此方法才有效...
还有其他方法吗？
我对接下来的问题更加困惑：
b）您的算法的运行时间是多少？给出答案。
c）背包是Karp NP完全问题之一。两种动态编程解决方案均导致多项式时间算法。为什么这与背包的NP完整性不矛盾？
A部分：由于所有项目的值都是正整数，因此不能破坏项目，这意味着必须将这些项目作为一个整体对待或留在后面，这是0/1背包问题的一个示例。此问题缺少贪婪选择属性，因此无法通过贪婪方法解决。必须进行动态编程。
例如，我们有第1项（总价值：$ 60，重量：10lbs，价值/重量：$ 6 / lb），第2项（总价值：$ 100，重量：20lbs，价值/重量：$ 5 / lb），和项目3 ：（总价值：$ 120，重量：30lbs，价值/重量：$ 4 / lb）。
用贪婪的方法，您首先将最有价值的物品拿走。项目1+项目2 = $ 160。这不是最佳解决方案，因为如果包含项目1，则其他项目可能会被迫退出，并可能会留有空白空间。必须查看具有项目1的解决方案与没有项目1的解决方案。这称为重叠子问题。
对于最优解，我们的最后一项n在最优解A中，或者不是。
要找到最大值（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：值（N- {n}，C）
由于要尝试的子问题很多，因此创建一个表，其中#columns =背包的大小+ 1（即0 ... C，C是背包的大小），而#rows =输入的顺序是任意的。使用上面列出的规则（从C = 0开始）填写表格，并逐一查看表格中的每个项目。选择提供最高容量和最高总价值的组合。
B部分：算法的运行时间为O（（Cn）^ 2）。该表是“容量”ד项目数”。表中的每个元素都比较2个值（不包括元素n {sub k}和包括元素n {sub k}的最大值）。
C部分：0/1背包是NP完整的，并且背包的容量是多项式。这与背包问题的NP完备性并不矛盾，因为在许多情况下，容量为O（2 ^ n）。