2个城市搬家工人的动态规划最大利润

Question

有一家搬家公司。它在两个城市开展业务。他们希望利润最大化。给定的是代表两个城市的 2 个数组。每个数组中位置 i 的值表示该城市当天要赚取的最大利润。如果他们在第 i 天在城市 A 工作，在第 i+1 天在城市 B 工作，则在两个城市 c 之间旅行会产生相关成本。我们需要使用动态规划来找到要获得的最大利润。这是一个例子：

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

我认为这类似于加权间隔计划或子集总和问题（背包）。感谢任何帮助。

编辑：

我需要找到算法的递归关系、时间复杂度，然后证明其正确性。有什么想法吗？

Answer 1

我认为你可以在这里简单地使用自下而上的 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

Answer 2

为了更好地表示这个问题，

设 A 为利润矩阵，其中 A[c] 为城市 c 的利润数组（c = 0 为第一个城市，c = 1 为第一个城市第二，依此类推）。
设 P(i, c) 为截至并包括第 i 天的最佳利润，这样搬家公司在第 i 天最终到达城市 c。
令 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 是最大的。最大解有两种可能：

i-1

c

i-1 日，搬家者在另一个城市 c'。

现在您需要证明的是，上面定义的递归将为您提供这两种情况下的正确解决方案。

Answer 3

你想要一个 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 4

如果存在类似于示例的情况，您的解决方案将不起作用：

a={1,5,3,9}
b={6,2,3,1}
k=3

预计：20
你的输出：17

2个城市搬家工人的动态规划最大利润

Dynamic Programming Maximum Profit for Movers in 2 cities

algorithm

dynamic-programming

subset-sum