时间戳

首页 > 解决方案 > 大小为 K 的子集的积总和

c++ - 大小为 K 的子集的积总和

问题描述

给定一组 n 个元素，求最大为 k 的子集的乘积之和（k 是另一个整数）。

n 的范围在 1000 秒内，所以我需要比指数时间复杂度更快的东西。

我觉得这个问题可能会使用多项式 FFT 来解决，但我不确定。另外，请查看https://math.stackexchange.com/questions/786183/sum-of-multiplication-of-all-combination-of-m-element-from-an-array-of-n-element/788655 #788655

例如 ：

S : {1, 2, 3, 4, 5}

k = 2

那么，答案将是

1 + 2 + 3 + 4 + 5 + 1*2 + 1*3 + 1*4 + 1*5 + 2*3 + 2*4 + 2*5 + 3*4 + 3*5

非常感谢伪代码或只是一些关于如何更接近解决方案的指针。

标签： c++algorithmmath

解决方案

令 DP[i][j]：大小正好为 j 且仅包含第 [1~i] 个元素的子集的乘积之和。

那么 DP[i][j] = DP[i-1][j] + DP[i-1][j-1] * arr[i]

现在您可以在时间复杂度 O(NK) 上解决它。

== 编辑 ==

这是一个简单的代码。

int arr[1002]; /// The array where number is located
int DP[1002][1002];
int ans=0; /// final answer
DP[0][0] = 1;
for(int i=1; i<=n; i++){
    DP[i][0] = 1;
    for(int j=1; j<=i && j<=k; j++){
        DP[i][j] = DP[i-1][j] + DP[i-1][j-1] * arr[i];
    }
}
for(int i=1; i<=k; i++) ans+=DP[n][i];

推荐阅读