为什么要在无限制的背包中构造一维数组，而在0/1的背包中构造二维维？

Question

我看到在无限制背包的情况下构造了一维数组，在0/1背包的情况下构造了二维数组？为什么会这样？在参考动态编程时会问这个问题。

Answer 1

动态编程通过维护“状态”来工作，当然，您希望使用最小的变量来表示状态。

现在，这两个问题的不同之处在于，您可以在“无限制背包问题”中随意选择单个项目，但是，在“ 0-1背包问题”中，您只能选择一个项目。这意味着，我想包括我是否已经在0-1背包问题中从列表中选择了一个项目，但是在0-1背包问题中没有必要这样做。这正是0-1背包问题中第二维的原因。