我正在研究一个Geekforgeeks练习题。我想出了一个针对"最大小费计算器"问题的朴素递归解决方案。
问题定义是：
餐厅接受N个订单。 如果拉胡尔接受第 i 个命令，则获得 $A[i].如果 Ankit 接受此订单，则提示将是 $B[i] 一个订单 每人。拉胡尔最多接受X个订单。安吉特最多接受 Y 订单。 X + Y>= N. 找出总小费的最大可能金额 处理完所有订单后。
输入：
第一行包含一个整数，即测试用例数。第二个 行包含三个整数 N、X、Y。第三行包含 N 整数。第 i 个整数表示 Ai。第四行包含 N 整数。第 i 个整数表示 Bi。
输出：打印一个整数，代表他们的最大小费 会收到。
我的代码和工作示例：
def max_tip(N, A, B, X, Y, n= 0):
if n == len(A) or N == 0:
return 0
if X == 0 and Y > 0: # rahul cannot take more orders
return max(B[n] + max_tip(N - 1, A, B, X, Y - 1, n + 1), # ankit takes the order
max_tip(N, A, B, X, Y, n + 1)) # ankit does not take order
elif Y == 0 and X > 0: # ankit cannot take more orders
return max(A[n] + max_tip(N - 1, A, B, X - 1, Y, n + 1), # rahul takes the order
max_tip(N, A, B, X, Y, n + 1)) # rahul does not take order
elif Y == 0 and X == 0: # neither can take orders
return 0
else:
return max(A[n] + max_tip(N - 1, A, B, X - 1, Y, n + 1), # rahul takes the order
B[n] + max_tip(N - 1, A, B, X, Y - 1, n + 1), #ankit takes the order
max_tip(N, A, B, X, Y, n + 1)) # nobody takes the order
T = int(input())
for i in range(T):
nxy = [int(n) for n in input().strip().split(" ")]
N = nxy[0]
X = nxy[1]
Y = nxy[2]
A = [int(n) for n in input().strip().split(" ")]
B = [int(n) for n in input().strip().split(" ")]
print(max_tip(N, A, B, X, Y))
我已经注释了我的递归调用决策。本质上，我将 0-1 背包的朴素解决方案扩展到另一个维度，两个服务员，要么一个接受，另一个接受，或者两者都不接受订单，具体取决于订单左侧约束。
解决方案检查器抱怨以下测试用例：
Input:
7 3 3
8 7 15 19 16 16 18
1 7 15 11 12 31 9
Its Correct output is:
110
And Your Code's Output is:
106
这让我感到困惑，因为最佳解决方案似乎是我的代码得到的 (19 + 16 + 18) + (7 + 15 + 31)。眼前的问题似乎是 X + Y <N。我的想法是我的代码也应该适用于>
这是怎么回事？
您正在考虑这种情况，没有人接受提示。但这种情况并不存在 X+Y>= n。这个java代码对我有用，看看。
private static int getMaxTip(int x, int y, int n, int[] A, int[] B) {
int[][] dp = new int[x + 1][y + 1];
dp[0][0] = 0;
for (int i = 1;i <= x;i++) {
dp[i][0] = (i <= n) ? dp[i - 1][0] + A[i - 1] : dp[i - 1][0];
}
for (int i = 1;i <= y;i++) {
dp[0][i] = (i <= n) ? dp[0][i - 1] + B[i - 1] : dp[0][i - 1];
}
for (int i = 1;i <= x;i++) {
for (int j = 1;j <= y;j++) {
if (i + j <= n) {
dp[i][j] = Math.max(dp[i - 1][j] + A[i + j - 1], dp[i][j - 1] + B[i + j - 1]);
}
}
}
int ans = Integer.MIN_VALUE;
for (int i = 0;i <= x;i++) {
for (int j = 0;j <= y;j++) {
if (i + j == n) {
ans = Math.max(ans, dp[i][j]);
}
}
}
return ans;
}
您正在考虑一种情况，即没有人采用不应该考虑的顺序，因为问题中提到了x+y>=n总是。删除该条件将起作用。
我假设，这是你的问题来源： https://practice.geeksforgeeks.org/problems/maximum-tip-calculator/0
这是我用 Python 编写的解决方案，通过了所有情况： https://github.com/Madhu-Guddana/My-Solutions/blob/master/adhoc/max_tip.py
解释： 压缩提示的相应元素并创建新数组。 根据 Rahul 和 Ankit 的差异量值对新数组进行排序， 然后我们可以安全地考虑数组两端的元素，哪一端会带来更多的利润，将值相加以计数。