Dynami c Программирование Максимальная прибыль для грузчиков в 2 городах

Question

Есть движущаяся компания. Работает в двух городах. Они будут sh, чтобы максимизировать прибыль. Дано 2 массива, представляющих два города. Значение в позиции i в каждом из массивов указывает максимальную прибыль, которую можно получить в городе в тот день. Если они работают в городе A в день i, а в городе B в день i + 1, то есть расходы, связанные с поездками между двумя городами c. Нам нужно использовать Dynami c Programming, чтобы найти максимальную прибыль, которую можно получить. Вот пример:

A = {10, 20, 30}
B = {-10, 50, 20}
c = 20
optimal solution = (10 + (50 - 20) + 20) = 10 + 30 + 20 = 60

Я думаю, что это похоже на график взвешенного интервала ИЛИ проблему с суммой подмножеств (рюкзак). Любая помощь приветствуется.

РЕДАКТИРОВАТЬ:

Мне нужно найти отношение (я) повторения, сложность алгоритма во времени и затем доказать правильность. Есть идеи?

Answer 1

Чтобы лучше представить эту проблему,

• Пусть A - матрица прибыли, где A[c] - массив прибыли для города c (c = 0 для первого города, c = 1 для второго и т. д.).
• Пусть P(i, c) будет оптимальной прибылью вплоть до дня * 1012 включительно, так что движущаяся компания окажется в городе c в день i.
• Пусть C(c', c) - это стоимость переезда из города c' в город c.

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

Чтобы максимизировать P(i, c), мы должны рассмотреть все возможные города, которые могут быть использованы грузчиками. в предыдущий день i-1 и выберите максимальный вариант. Эти возможности включают перевозчиков, которые находились в том же городе в предыдущий день, и переезжали из другого города в предыдущий день, в то же время оплачивая транспортные расходы. Следовательно,

P(i, c) = max(P(i-1, c), max(P(i-1, c') + C(c', c) for all cities c' != c)) + A[c][i]

Первый аргумент во внешнем max (P(i-1, c)) рассматривает случай, когда грузчики были в том же городе в предыдущий день, и второй аргумент (внутренний max). ) оценивает и максимизирует прибыль (включая транспортные расходы), если грузчики были в другом городе в предыдущий день.

Окончательный ответ - просто max(P(n, x) for all cities x), где n - последний день (учитывая все возможные города, в которых могут оказаться грузчики в последний день).

В вашем примере, город A == город 0, город B == город 1, матрица прибыли A = [[10, 20, 30], [-10, 50, 20]] и C(0, 1) = C(1, 0) = 20.

РЕДАКТИРОВАТЬ:

Сложность времени будет O(nc), где n - количество дней, а c - количество городов. Если число городов фиксировано, то временная сложность составляет O(n).

Доказательство правильности может быть сделано с помощью индукции. Предположим, что P(i-1, x) является максимальным для всех городов x. Затем покажите, что P(i, c) для некоторого города c, как определено выше, является максимальным. Существует два варианта максимального решения:

• Грузчики были в одном городе c в день i-1
• Грузчики были в другом городе c' на день i-1.

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

Answer 2

Вы хотите решение DP, но я думаю, что жадный подход больше подходит для этой проблемы. вот жадное решение:

        int[] a = new int[] { 10, 20, 30 };
        int[] b = new int[] { -10, 50, 20 };

        int n = a.Length;
        bool aSelected = a[0] > b[0];
        int c = 20;
        int profit = Math.Max(a[0], b[0]);
        for (int i = 1; i < n; i++)
        {
            int temp;
            if (aSelected)
            {
                temp = Math.Max(a[i], b[i] - c);
                if (temp != a[i])
                {
                    aSelected = false;
                }
            }
            else
            {
                temp = Math.Max(a[i] - c, b[i]);
                if (temp != b[i])
                {
                    aSelected = true;
                }
            }

            profit += temp;
        }
        Console.WriteLine(profit);

Answer 3

Я думаю, что вы можете просто использовать восходящий DP здесь.

Держите оптимальные субрешения справа налево. Для каждого нового элемента, скажем, массив A равен

dp1[i] = Math.max(A[i] + dp1[i+1],A[i] + dp2[i+1] - C);

, где dp1 - максимум, который нужно сохранить для массива A, а dp2 - максимум, который нужно сохранить для массива B.

Фрагмент:

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) {
        int[] A = {10,20,00};
        int[] B = {-10,50,20};
        int C = 20;
        System.out.println(solve(A,B,C));
    }

    private static int solve(int[] A,int[] B,int C){
        int len = A.length;
        int[] dp1 = new int[len];
        int[] dp2 = new int[len];
        dp1[len-1] = A[len-1];
        dp2[len-1] = B[len-1];
        int max = Math.max(dp1[len-1],dp2[len-1]);
        for(int i=A.length-2;i >= 0;--i){
            dp1[i] = Math.max(A[i] + dp1[i+1],A[i] + dp2[i+1] - C);
            dp2[i] = Math.max(B[i] + dp2[i+1],B[i] + dp1[i+1] - C);
            max = Math.max(dp1[i],dp2[i]);
        }
        return max;
    }

}

Демонстрация: https://onlinegdb.com/BJFptkHDU