gpt4 book ai didi

python - 最大小费计算器 - 天真的解决方案

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:04:44 31 4
gpt4 key购买 nike

我正在做一个 Geekforgeeks 练习题。我想出了一个简单的递归解决方案来解决“最大小费计算器”问题。

问题定义是:

Restaurant recieves N orders. If Rahul takes the ith order, gain $A[i]. If Ankit takes this order, the tip would be $B[i] One order per person. Rahul takes max X orders. Ankit takes max Y orders. X + Y >= N. Find out the maximum possible amount of total tip money after processing all the orders.

Input:

The first line contains one integer, number of test cases. The second line contains three integers N, X, Y. The third line contains N integers. The ith integer represents Ai. The fourth line contains N integers. The ith integer represents Bi.

Output: Print a single integer representing the maximum tip money they would receive.

我的代码和工作示例:

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 的情况。

这是怎么回事?

最佳答案

您正在考虑没有人收取小费的情况。但这种情况不存在,因为 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;
}

关于python - 最大小费计算器 - 天真的解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48245860/

31 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com