Динамическое программирование, находящее максимальное значение продуктов и сумму для элементов в массиве

Question

Привет у меня есть следующая проблема, которую я хочу реализовать:

заданный массив целых чисел: 1 2 7 5 1 2Я хочу найти максимальную сумму смежных товаров, т.е. 1+2+(5*7)+1+2 = 41

данный массив целых чисел: 1 2 4 2 4 2 Я хочу найти максимальную сумму смежных произведений, т.е. 1+(2*4)+(2*4)+2 = 19

Ограничение на умножение состоит в том, что только один соседний элемент может быть использован для умножения. т.е. если у нас есть 2 4 2 в массиве мы будем вычислять его как 2+(4*2) or (2*4)+2,

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

Кто-нибудь может предложить что-нибудь?

Answer 1

Пошаговое решение выглядит так:

• рассмотрим первый элемент, он максимален, когда нет другого элемента.
• пока все ваши элементы не там, продолжайте.
• добавить i-й элемент:
  • F(i) = Макс {F (i-1) + e _i, f (i-2) + e _i-1 * e _i)

где F(i) - ваш максимум для первых элементов i, а e _i - ваш _i- й элемент.

Учти это: 1 2 4 3 4

• сначала мы имеем F(1) = 1,
• затем F(2) = 1 + 2,
• тогда мы сравниваем F(2) + 4 = 1 + 2 + 4 а также F(1) + 2 * 4= 1 + 2 * 4 так что, это F(3) = 1+2*4 = 9,
• тогда у вас есть F(2) + 4 * 3 = 1 + 2 + 4 * 3 а также F(3) + 3 = 1 + 2 * 4 + 3 так что, это F(4) = 1 + 2+ 4*3 = 15
• тогда у вас есть F(4) + 4 = 1 + 2 + 4 * 3 + 4 а также F(3) + 3*4 = 1 + 2 * 4 + 3 * 4 так что, это F(5) = 1 + 2 * 4 + 3 * 4 = 21

Answer 2

Я публикую полное решение Java для этой проблемы. Добавлены встроенные комментарии для реализованной логики.

public class MaxValueOfRagularExpression {

    public static void main(String[] args) {
        int size=6;
        int arr[] = new int[size];

        arr[0]=2;
        arr[1]=1;
        arr[2]=1;
        arr[3]=1;
        arr[4]=1;
        arr[5]=2;

        // array elements are as follows :
        // A0     A1    A2      A3    A4     A5
        // 2      1      1      1     1      2

        int sol[] = new int[size];
        sol[0]=arr[0];
        for(int i = 1;i<size;i++){
            // sol[i] would contain the optimized value so far calculated.
            for(int k = 0;k<i ;k++) {
                // for each k , find sum of all array elements  i.e. k+1<=j<=i
                // and then calculate max of (sol[k] + sum or sum[k] * k )
                int sum =0;
                for (int j = k+1; j <= i; j++) {
                    sum += arr[j];
                }
                sol[i] = Math.max(Math.max(sol[i],(sol[k] + sum)), sol[k]*sum);
            }
        }
        // after processing above block , the sol array will look like :
        //SOL[0]  SOL[2]   SOL[2]   SOL[3]   SOL[4]   SOL[5]
        // 2        3       4        6          9     18
        System.out.println(sol[size-1]);
    }
}