在动态规划解决背包问题时,若物品的重量和价值均为整数,背包容量为W,物品数量为N。以下哪种方法可以在时间复杂度为O(NW)的情况下,准确求出背包能装下的最大价值?
答案解析
选项A和D虽然都能准确求出最大价值,但它们的时间复杂度为O(NW),空间复杂度也为O(NW),没有利用到动态规划的空间优化技巧。选项C通过顺序更新dp数组,会导致同一物品被多次考虑,从而无法保证结果的准确性。选项B通过逆序更新dp数组,确保了每个物品只被考虑一次,同时实现了空间复杂度为O(W)的优化,因此是正确答案。
正确答案:B