有一家搬家公司在两个城市运营。他们希望最大化利润。给定两个代表两个城市的数组。数组中每个位置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
我认为这与加权区间调度问题或子集和问题（背包问题）相似。非常感谢您提供的任何帮助。
编辑:
我需要找到递归关系，算法的时间复杂度，并证明其正确性。有什么想法吗？
A为利润矩阵，其中A[c]是城市c的利润数组（对于第一个城市，第二个城市等等）。 P(i, c)为包括第i天在内，在第i天结束时搬家公司位于城市c的最佳利润。 C(c', c)是从城市c'到城市c的移动成本。 这种设置使我们能够将解决方案推广到任意数量的城市。
为了最大化P(i, c)，我们必须考虑搬家工人可能在前一天处于的所有城市，并选择最大的选项。这些可能性包括搬家工人在前一天在同一个城市，以及从另一个城市移动前一天，并承担搬家成本。因此
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)。
使用归纳法可以证明正确性。假设对于所有城市 x，P(i-1, x) 都是最大的。然后证明对于一些城市 c，根据上述定义的 P(i, c) 最大。最大解有两种可能：
i-1 天，搬家工人在城市 c 中i-1 天，搬家工人在城市 c' 中现在您需要证明，递归定义将在这两种情况下都给出正确的解。
我认为你可以在这里简单地使用自底向上的动态规划。
从右到左保留最优子解。对于每个新元素，比如数组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;
}
}
你想要一个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);
如果有像例子中一样的相等情况，你的解决方案就不起作用了：
a={1,5,3,9}
b={6,2,3,1}
k=3