2

我正在尝试对我的 TI-83 进行编程以进行子集总和搜索。所以，给定一个长度为 N 的列表，我想找到所有给定长度 L 的列表，总和为给定值 V。

这与常规子集和问题有点不同，因为我只搜索给定长度的子集，而不是所有长度，并且递归不一定是首选，因为我无法调用我正在工作的程序。

我可以使用嵌套循环轻松完成任务，但是对于大于 5 的 L 值，这变得很麻烦。我正在尝试动态解决方案，但没有得到任何结果。

真的，在这一点上，我只是想让列表引用正确，所以这就是我正在寻找的。让我们举个例子：

L1={p,q,r,s,t,u}

所以

N=6

让我们寻找长度为 3 的所有子集以使其相对较短，因此 L = 3（6c3 = 20 个总输出）。

理想情况下，要搜索的列表引用是：

{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,3,4}
{1,3,5}
{1,3,6}
{1,4,5}
{1,4,6}
{1,5,6}
{2,3,4}
{2,3,5}
{2,3,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,5}
{3,4,6}
{3,5,6}
{4,5,6}

显然是通过以下方式完成的：

FOR A,1,N-2
    FOR B,A+1,N-1
        FOR C,B+1,N
            display {A,B,C}
        END
    END
END

我最初对 N 的数据进行降序排序，这允许我搜索缩短搜索的条件，并且当我在循环中增加 A、B 和 C 的值时，使用 FOR 循环在不同的地方把它搞砸了。

我也在寻找更好的动态解决方案。我已经在网络上进行了一些研究，但我似乎无法根据我的特定情况调整那里的内容。

任何帮助，将不胜感激。我试图保持足够简短，以免写小说，而是解释我想要了解的内容。我可以根据需要提供更多详细信息。

4

1 回答 1

1

为了优化，您只需跳过那些您现在已经超过值 V 的搜索子树。递归是要走的路，但是，由于您已经排除了这一点，您将成为最好设置允许深度的上限。

我会选择这样的东西（深度为 3）：

N is the total number of array elements.
L is the desired length (3).
V is the desired sum
Y[] is the array
Z is the total

Z = 0
IF Z <= V
  FOR A,1,N-L
    Z = Z + Y[A]
    IF Z <= V
      FOR B,A+1,N-L+1
        Z = Z + Y[B]
        IF Z <= V
          FOR C,B+1,N-L+2
            Z = Z + Y[C]
            IF Z = V
              DISPLAY {A,B,C}
            END
            Z = Z - Y[C]
          END
        END
        Z = Z - Y[B]
      END
    END
    Z = Z - Y[A]
  END
END

现在这非常令人费解，但它基本上在每个阶段检查您是否已经超过所需值，并且拒绝检查较低的子树作为效率措施。它还保留当前级别的运行总计，以便在检查较低级别时不必进行大量添加。这是对 Z 的数组值的加法和减法。

当您修改它以处理更多深度时，它会变得更加复杂（通过使用变量 fromD到K11 个级别（如果您愿意移动N和L向下移动W，X或者如果 TI BASIC 允许变量名称中有多个字符，则更复杂） ）。

我能想到的唯一其他非递归方式是使用一组值组来模拟迭代递归，这看起来只会稍微少一些（尽管代码应该少嵌套）。

于 2009-12-29T04:28:08.383 回答