<分区>
我知道如何使用动态规划方法解决背包 0-1 问题，但我在确定要带哪些元素而不影响 O(N * C)(N 件元素，C 容量)的复杂性时遇到了麻烦。
有什么想法(我更喜欢自下而上的方法)吗？
<分区>
我知道如何使用动态规划方法解决背包 0-1 问题，但我在确定要带哪些元素而不影响 O(N * C)(N 件元素，C 容量)的复杂性时遇到了麻烦。
有什么想法(我更喜欢自下而上的方法)吗？
最佳答案
假设，现在您正在将结果存储在数组 bool[] a 中，其中 a[i] 为 true 时 sum i可以实现。
您将需要另一个数组 int[] b，其中 b[i] 是您放入背包中以实现总和 i 的最后一个元素>.
那么，你在哪里
a[i] = true;
你需要
a[i] = true;
b[i] = current_item;
然后，找到可以取哪些项目来实现 sum i 是一个简单的循环。
PS 为了简单起见，我使用了两个数组，但显然可以删除数组 a。
关于algorithm - Knapsack 0-1路径重构(带哪些元素)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4935533/