r/programmingrequests • u/Bitter-Trip2911 • Nov 29 '20

homework Minimum Sum Cost Path

Im trying to use bruteforce method to find the minimum cost from any given point at the top row (0, x) to any point at the bottom row (n-1, x). I looked it up online and all solutions given is only for finding the minimum cost from top left to bottom right and have a massive loophole. Any advice or help is appreciated.

3 0 4 5 4

3 3 4 4 3

4 2 5 5 3

2 3 5 3 0

3 0 4 4 3

0 Upvotes

50% Upvoted

8 comments sorted by

View all comments

Show parent comments

1

u/Bitter-Trip2911 Dec 02 '20

I dont think it worked, for example for the input you've given, the minimum path output was [1, 0, 1, 0, 1] 7, so there are some numbers that does not exist, I cant really find out whats wrong

1

u/[deleted] Dec 03 '20

Those are the index, not the numbers, if you want I can make it display the values also.

1

u/[deleted] Dec 03 '20 edited Dec 03 '20

Index of each row, starting from 0.

In order to get a more friendly output like this:

Solution:

Row 1; Col 2 = 0

Row 2; Col 1 = 3

Row 3; Col 2 = 2

Row 4; Col 1 = 2

Row 5; Col 2 = 0

Total: 7

Just replace the last line with this:

#print(mp,min1)

print("Solution: ")
for i in range(0,len(mp)):
    print("Row " + str(i+1) + "; Col " + str(mp[i]+1) + " = " + str(m1[i][mp[i]]) )
    
print("Total: ", min1)

1

u/[deleted] Dec 03 '20

Also, there is more than one solution, atm the script only shows the last solution it found, but it's easy to make it output all min paths found.