Определить максимальную сумму ключей подмассивов с заданной максимальной величиной

Question

Я, имеющей два двумерный массивом следующим образом: в паре

3,3 
4,3 
3,2 
2,2 
2,1 

Теперь я хочу, чтобы выяснить, подмассив с максимальной суммой ключей и чья сумма значений = 6

разные подмассивы со значениями sumof 6 являются

[[3,3],[4,3]] ,Sum = 7 
[[3,3],[3,2],[2,1]] ,Sum = 8 
[[3,3],[2,2],[2,1]] ,Sum = 7 
[[4,3],[3,2],[2,1]],sum = 9 
[[4,3],[2,2],[2,1]],sum =8 

для указанных выше элементов массива [4,3] [3,2], [2,1] форма подмассив с суммой значений, т.е. 6 3 + 2 +1 = 6 Сумма ключей выше подмассивов = 9, что является максимальным

Я не в состоянии правильно думать, если она может решить DP или основных указателей iteration.Any/советы помогут

Answer 1

Это может быть решена с помощью динамического программирования , мы можем перебирать по каждому индексу и можем либо добавить текущий указатель к ответу, либо выбрать его игнорировать, тогда вы можете смириться, чтобы уменьшить сложность проблемы.

Я написал рекурсивную динамического программирования решение в C++:

#include <iostream> 
#define INF 100000000 
using namespace std; 

int arr[100][2], sumOfValues, n, dp[100][10000]; 

int solve(int index, int currentSum){ 
    if(index == n){ 
     if(currentSum == sumOfValues) return 0; 
     else return -INF; 
    } 
    if(dp[index][currentSum] != -1) return dp[index][currentSum]; 
    int v1 = solve(index+1, currentSum + arr[index][1]) + arr[index][0]; //take current element 
    int v2 = solve(index+1, currentSum); //do not take current element 
    return dp[index][currentSum] = max(v1, v2); 
} 

int main() { 
    n = 5; 
    sumOfValues = 6; 
    arr[0][0] = 3;arr[0][1] = 3; 
    arr[1][0] = 4;arr[1][1] = 3; 
    arr[2][0] = 3;arr[2][1] = 2; 
    arr[3][0] = 2;arr[3][1] = 2; 
    arr[4][0] = 2;arr[4][1] = 1; 
    for(int i = 0;i < 100;i++) for(int j = 0;j < 10000;j++) dp[i][j] = -1; 
    cout << solve(0, 0) << endl; 
    return 0; 
} 

Ссылка на решение на Ideone: http://ideone.com/HMw9Sf

Заметьте, что если ответ Возвращается -INF, что означает, что никакое решение не было возможности данные sumOfValues.