3

我有一个包含 n 个元素的数组 A。我想找出数组 A 的所有子数组中所有元素的乘法。我期待在 DP 的帮助下实现该解决方案。我想将所有产品值存储在数组 B 中。我是编程的初学者。我做了很多谷歌搜索，但我无法找到我的查询的确切解决方案。任何人都可以帮我提供问题的逻辑。例子：

A={1,2,3}

所有可能的子数组都是

{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

所以所有可能的产品都是

{1,2,3,2,3,6,6}

分别。

任何帮助都是可观的。提前致谢。

4

4 回答 4

0

这可能会有所帮助：

在每种情况下，您都必须做出两个选择：

要么选择当前子数组中的数组元素，要么不选择。以下递归可能会有所帮助：

f(i,p)=f(i+1,p*arr[i])||f(i+1,p)

于 2015-10-10T07:38:08.890 回答
0

提示您自己尝试将是这样的。考虑到我们在一个数组中有 N 个元素的事实。这些元素可能是唯一的，也可能不是唯一的。然后我们创建一个二进制数字列表/数组来映射所有可能的子数组（尽管根据您的疑问，正确的术语应该是子序列）。

For example : 
here N = 4.
Array : 1 2 3 2

The possible sub sequences would be

Binary Encoding (1 to include, 0 to exclude) :
0 0 0 0 : {}     # No use for us in this case
0 0 0 1 : {2}
0 0 1 0 : {3}
0 0 1 1 : {3, 2}
0 1 0 0 : {2}
0 1 0 1 : {2,2}
0 1 1 0 : {2,3}
0 1 1 1 : {2,3,2}
1 0 0 0 : {1}
1 0 0 1 : {1,2}
1 0 1 0 : {1,3}
1 0 1 1 : {1,3,2}
1 1 0 0 : {1,2}
1 1 0 1 : {1,2,2}
1 1 1 0 : {1,2,3}
1 1 1 1 : {1,2,3,2}


Thus you can generate all the sub sequences for a given array. and find their product.
于 2020-04-04T14:24:37.613 回答
0

M-size set有N = 2^M-1子集（包括空集），所以每个子集对应 range 中的数字0..N-1。如果第 k 位设置为某个数字，则第 k 个元素出现在相应的子集中。

动态编程方法允许重用计算的产品，因此复杂度与输出大小成线性关系 O(N) = O(2^M)
Delphi 代码：

var
  A, Prods: TArray<Integer>;
  iA, i, SeriesLen, N: Integer;
  s: String;
begin
  A := TArray<Integer>.Create(2, 3, 5, 7);
  N := 1 shl Length(A); //output array size = 2^InputLength

  SetLength(Prods, N);
  Prods[0] := 1;
  SeriesLen := 1;
  for iA := 0 to Length(A) - 1 do begin
    for i := 0 to SeriesLen - 1 do
      Prods[i + SeriesLen] := Prods[i] * A[iA];
    SeriesLen := SeriesLen * 2;
  end;

output Prods[1]..Prods[N-1]

Result: 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210
于 2015-10-10T11:37:50.387 回答
0

您可能知道如何创建数组的所有子数组，因此，这使问题变得简单：

如果你有n元素array(a)并且其中一个元素是m，那么为了计算你的问题，你可以使用这个：

MySubArray(a , n) = new array{ MySubArray(a - {m} , n - 1) , MySubArray(a - {m} , n - 1) * m};

这意味着您一次计算所有子数组的问题a - {m}，另一次，您添加m所有这些，然后将它们的乘积乘以m.

于 2015-10-10T07:48:32.740 回答