最大化一個數組的總和，同時保持其他數組的相應元素的和小於k

Question

我有兩個數組，我必須從第一個數組中選擇一些元素，以使它們的總和最大化，而相應元素的總和第二陣列小於k。

我現在可以想到一個遞歸的解決方案，我需要一個迭代解決方案。

例如：

陣列1：2 2 5 4 3 6 10

陣列2：4 3 2 5 4 10 7且k = 15

所有數字都是正的。

Answer 1

該陣列的每個元素都可能丟失，從而導致2^N組合被評估。例如，您可以生成0到2^N-1之間的數字，並將它們的各個位用作此類存在/不存在的指示符。

整個溶液可以通過將本Python的單行中找到（被分爲這裏三行）：

import itertools 

a1 = [2, 2, 5, 4, 3, 6, 10] 
a2 = [4, 3, 2, 5, 4, 10, 7] 
k = 15 

print sorted((sum(itertools.compress(a1, s)), s) 
    for s in itertools.product([0, 1], repeat=len(a1)) 
     if sum(itertools.compress(a2, s)) < k)[-1][1] 

Answer 2

假設每個陣列具有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是多大來選擇不同的算法。