algorithm - 背包算法可以在列主要形式中实现吗？

Question

我在网上搜索了背包算法，在所有的实现中，我看到二维数组的形式是:

 int K[n+1][W+1];

其中 n 是元素的数量，W 是背包中可以容纳的最大重量。

这个数组以自下而上的方式填充，以行主要格式。它甚至可以以专栏主要格式完成吗？

Answer 1

对数组填充顺序的唯一要求是，如果 a <= b 且 c <= d，则 (a,c) 单元格不会在 (b,d) 单元格之后填充。这是跟踪动态程序的数据依赖关系得出的。行优先、列优先和许多其他填充顺序都是可能的。