Saturday, June 25, 2016

get max profit given matrix of profit for days and pachinkos

//matrix
 --days-->
|
pachinkos
|

//example
   d1 d2 d3
p1 -1  2  1
p2  1 -1  2
p3 -2  1  3
constraints:
- only 1 pachinko per day
- from pachinko i, only pachinkos i-1 and i+1 can be visited
- from last pachinko, first pachinko can be visited and vice versa
- pachinko can be visited only once

note:
- the recursive function returns null instead of 0 as matrix has -ve profits.
(matrix):
    if matrix == null || matrix.length() == 0 || matrix[0].length() == 0:
        throw //or return null
    maxprofit = null
    days = matrix.length()
    pachinkos = matrix[0].length()
    bool[] visited = new
    for pachinko = 0, pachinko < pachinkos, pachinko++:
        profit = (matrix, day: 0, days, pachinko, pachinkos, visited)
        if maxprofit == null || profit > maxprofit:
            maxprofit = profit
    return maxprofit

int? (matrix, day, days, pachinko, pachinkos, visited):
    if day == days:
        return null
    if !(0 <= day < days):
        return null
    if pachinko == -1:
        pachinko = pachinkos-1
    if pachinko == pachinkos:
        pachinko = 0
    if !(0 <= pachinko < pachinkos):
        return null
    if visited[pachinko]:
        return null
    profit = matrix[day][pachinko]
    visited[pachinko] = true
    maxNextDayProfit = null
    nextdayProfit = (matrix, day+1, days, pachinko-1, pachinkos, visited)
    if maxNextDayProfit == null || nextdayProfit > maxNextDayProfit:
        maxNextDayProfit = nextdayProfit
    nextdayProfit = (matrix, day+1, days, pachinko+1, pachinkos, visited)
    if maxNextDayProfit == null || nextdayProfit > maxNextDayProfit:
        maxNextDayProfit = nextdayProfit
    if maxNextDayProfit != null:
        profit += maxNextDayProfit
    visited[pachinko] = false
    return profit
[Hat tip to SM]

No comments:

Post a Comment