我正在审查即将进行的测试，并想知道是否有人可以重述问题的 b 部分。这是通过的审查表中的文字，但我不确定 b 部分到底在问什么。我更严格地猜想“产生的解决方案小于 0/1 背包问题的最佳解决方案的 1%”是什么意思。
a) 解决以下背包问题的例子，即给出每个选择的对象的分数和最佳背包的值。显示步骤：
背包容量为 C = 100
** 他在这里列出了对象、它们的值和权重。在表中**
b) [10pts] 举一个包含两个对象的示例，表明用于分数背包问题的相同贪心方法（稍作修改以省略贪心方法选择的最后一个对象，如果它不适合）产生的解决方案是小于 0/1 背包问题的最优值的 1%。
通常，贪婪启发式对于背包问题非常有效。如果您只是随机提出一个小问题实例，那么应用贪心启发式可能会产生一个好的，甚至可能是最优的解决方案。（解决方案的质量是通过取其包含的对象的总值，并计算其与最优解决方案中包含的对象的总值之比来衡量的。）
这个问题要求你想出一个令人讨厌的问题实例（即具有值和权重的对象列表），它使贪婪启发式算法非常混乱，以至于应用它会产生一个背包，其中仅包含最佳解决方案将包含的值的 1% .
我理解 b) 部分要求表明贪心算法不是最优的，而且可以产生不到最优值的 1%。小型实例已经是这种情况。考虑以下实例：
Item 1: profit 2, weight 1 (efficiency is 2/1 = 200/100 = 2)
Item 2: profit 400, weight 400 (efficiency is 400/400 = 1)
Knapsack capacity: 400
请注意，这些项目是按效率的非递增顺序给出的，这是贪心算法处理它们的顺序。现在贪心算法会选择第 1 项，因为它适合，但现在第 2 项无法选择。这会产生 2 的利润。但是，选择项目 2 会产生 400 的利润。总的来说，贪心算法产生的利润为 2，其中最优值至少为 400，因此贪心算法产生的利润不到最优利润。
背包问题属于NP。我认为第二部分要求基于贪心策略的多项式时间逼近算法（其中最优解具有指数时间复杂度），它给出的解与最优解仅相差 1%。
例如，如果最佳答案是 100，则近似算法应给出 99 或 101 的结果。