[Python] Python - Algorithm to maximize profit with refueling constraints and optional...

I've implemented an algorithm that works correctly for some of the provided test cases (Test 1, 2, 3, 4, and 5) but returns incorrect values for the last two tests (Test 6 and 7). I need help identifying what might be wrong in my approach or suggestions on how to improve the algorithm so that it returns the correct number.

def max_money(K, D, C, P):
N = len(D)
dp = [[-float('inf')] * 2 for _ in range(N)]

dp[0][1] = P[0]

for i in range(1, N):
for j in range(i):
distance = D - D[j]
if distance <= K:
if dp[j][0] >= 0:
if dp[j][0] >= C:
dp[0] = max(dp[0], dp[j][0] - C)
if i != N - 1:
dp[1] = max(dp[1], dp[j][0] + P)
if dp[j][1] >= 0:
if dp[j][1] >= C:
dp[0] = max(dp[0], dp[j][1] - C)
if i != N - 1:
dp[1] = max(dp[1], dp[j][1] + P)

if N == 1:
return dp[0][1]

final_money = dp[N-1][0]

return final_money if final_money >= 0 else -1

# Examples to test
examples = [
(50, [0], [50], [100], 100),
(50, [0, 20], [50, 50], [100, 100], 50),
(50, [0, 20, 30], [50, 50, 40], [100, 100, 200], 160),
(50, [0, 80], [50, 50], [100, 100], -1),
(50, [0, 10], [50, 150], [100, 100], -1),
(100, [0, 50, 100, 150], [50, 30, 30, 30], [100, 100, 200, 150], 240),
(100, [0, 50, 100, 150, 200], [50, 110, 30, 30, 40], [100, 100, 200, 150, 50], 280)
]

# Running tests and printing detailed results
for idx, (K, D, C, P, expected) in enumerate(examples, 1):
result = max_money(K, D, C, P)
print(f"Test case {idx}: Expected {expected}, Got {result}")


Test case 1: Expected 100, got 100
Test case 2: Expected 50, got 50
Test case 3: Expected 160, got 160
Test case 4: Expected -1, got -1
Test case 5: Expected -1, got -1
Test case 6: Expected 240, got 370
Test case 7: Expected 280, got 510

Continue reading...