我有一个包含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}
分别。希望能得到帮助,谢谢。
我有一个包含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}
这可能会有所帮助:
在每个实例中,您必须做出两个选择:
要么选择当前子数组中的数组元素,要么不选择。以下递归可能会有所帮助:
f(i,p)=f(i+1,p*arr[i])||f(i+1,p)
你可能知道如何创建数组的所有子数组,因此这使问题变得容易:
如果你的array(a)
中有n
个元素,并且其中一个元素是m
,那么为了计算你的问题,你可以使用以下方法:
MySubArray(a , n) =
new array{ MySubArray(a - {m} , n - 1) , MySubArray(a - {m} , n - 1) * m};
这意味着你需要对a - {m}
的所有子数组计算一次问题,然后再将m
添加到所有子数组中并将它们的乘积乘以m
。
对于大小为M的集合(包括空集),有N = 2^M-1
个子集,因此每个子集对应于范围内的数字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
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.