我知道如何用动态规划方法解决背包 0-1 问题，但我很难弄清楚要拿哪些物品而不影响 O(N * C)（N 个物品，C 容量）的复杂性。
有什么想法（我更喜欢自下而上的方法）？
假设现在您将结果存储在数组中bool[] a, where a[i]当总和时为真i可以实现。
你需要另一个数组int[] b, where b[i]是您放入背包中以求和的最后一个元素i.
那么，你在哪里
a[i] = true;
你需要
a[i] = true;
b[i] = current_item;
然后找出哪些项目可以达到总和i是一个简单的循环。
PS 为了简单起见，我使用两个数组，但显然是数组a可以删除。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
