найти максимальную сумму п элементов в массиве таким образом, что не более чем к элементы примыкают

Question

Почти так же, как это: find maximum sum of elements in an array such that not more than k elements are adjacent

кроме есть предел п элементов мы можем выбирать. Как изменить алгоритм DP, чтобы он работал для этого?

Answer 1

хорошо, позвольте мне сделать это более четко.

вопрос: найти максимальную сумму п элементов в массиве таким образом, что не более K элементы являются смежными

пусть Int F [I] [J] [K] означает максимальную сумму для первого г элементов , используя j полных элементов и последние k элементов. let bool g [i] [j] [k] означает, можно ли получить определенную комбинацию. например. g [1] [1] [2] неверно. это важно, потому что без ограничения, f может генерировать невозможно ответов.

Первоначально memset f и g должны быть все нули и заданы g [0] [0] [0] как истина. мы можем использовать повторную рекурсию для решения этой проблемы DP. очевидно, каждый раз, когда вы сталкиваетесь с числом, у вас есть два варианта: выберите его или откройте его. Тэй выдает рекуррентную формулу:

f[i][j][k] can infer f[i+1][j+1][k+1], or 
f[i][j][k] can infer f[i+1][j][0] 

так, то псевдо-код может быть следующим:

memset(f,0,sizeof(f)); 
memset(g,0,sizeof(g)); 
g[0][0][0]=true; 
for (int i=0;i<array.size();i++) 
    for (int j=0;j<=n;j++) 
     for (int k=0;k<=K;k++) if (g[i][j][k]) { 
      f[i+1][j][0]=max(f[i+1][j][0],f[i][j][k]); 
      f[i+1][j+1][k+1]=max(f[i+1][j+1][k+1],f[i][j][k]+array[i]); 
      g[i+1][j][0]=true; 
      g[i+1][j+1][k+1]=true; 
     } 

и конечный результат будет:

ans=0; 
for (i=0;i<=K;i++) 
    ans=max(ans,f[array.size()][n][i]); 
return ans; 

выше, дает точно J элементы. если вы хотите получить в большинстве J элементов, вы можете изменить его таким образом:

ans=0; 
for (i=0;i<=n;i++) 
    for (j=0;j<=K;j++) 
     ans=max(ans,f[array.size()][i][j]); 
return ans; 

Answer 2

Добавить новое измерение функции DP: f[i, j, l] - максимальная сумма для первых я элементов, если они используются J общих элементов и последних индуктивных элементов в этой сумме.