arrays - 最大化一个数组的总和，同时保持另一数组对应元素的总和小于 k

Question

我有两个数组，我必须从第一个数组中选择一些元素，使它们的总和最大化，而第二个数组相应元素的总和小于 k。

到目前为止我能想到一个递归的解决方案，我需要一个迭代的解决方案。

例子:

数组 1 : 2 2 5 4 3 6 10

数组 2 : 4 3 2 5 4 10 7 和 k = 15

所有的数字都是正数。

Answer 1

假设每个数组有 n 个元素。一种解决方案是尝试 n 个元素的所有可能组合，这意味着时间复杂度为 O(2^n) .

而使用动态规划可以实现O(n*k)时间复杂度:

dp[i][j] = x表示对于前i个元素，从数组2中选择一些元素，数组2中被选中元素的和为j(0 <= j < k)，数组1中对应被选中元素的最大和为x。然后我们要 dp[n][j] (0 <= j < k) 最大值。

状态转移方程是尝试数组2的第i个元素是否被选中。如果未选择，dp[i][j] = dp[i-1][j] ;如果选中，dp[i][j] 可以是 max(dp[i-1][j], dp[i-1][j-b[i]] + a[i]) , 这里 b[i] <= j < k.

    for(int i=1;i<=n;i++) {
        for(int j=0;j<k;j++) {
            dp[i][j] = 0;
        }
    }
    if(b[1] < k) {
        dp[1][b[0]] = a[0];
    }
    for(i=2;i<=n;i++) {
        for(j=0;j<k;j++) {
            dp[i][j] = dp[i-1][j];
            if(j >= b[i] && dp[i-1][j - b[i]] + a[i] > dp[i][j]) {
                dp[i][j] = dp[i-1][j - b[i]] + a[i];
            }
        }
    }

答案是max(d[[n][j]), 0 <= j< k .

请根据大小选择不同的算法n和 k是。