Максимизируйте сумму одного массива, сохраняя при этом сумму соответствующих элементов другого массива меньше 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 элементов, что означает, что сложность времени равна O(2^n).

В то время как использовать динамическое программирование может достичь O(n*k) времени сложность:

dp[i][j] = x означает, что в течение первых я элементов, выбрать некоторые элементы из массива 2, а сумма выбранных элементов массива 2, у (0 < = J < k), максимальная сумма соответствующих выбранных элементов массива 1 равна x. Затем мы хотим dp[n][j] (0 < = j < k) максимум.

Уравнение перехода состояния состоит в том, чтобы попытаться выбрать i-й элемент массива 2. Если не выбран, 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.