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: profits can be -ve so maxprofit can be -ve so maxprofit cannot default to 0 so the null checks.

With backtracking:
int (matrix):
    if matrix == null || matrix.length() == 0 || matrix[0].length() == 0:
        throw //or return 0
    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.value:
            maxprofit.value = profit
    return maxprofit.value

int (matrix, day, days, pachinko, pachinkos, visited):
    if !(0 <= day <= days):
        throw
    if !(0 <= pachinko < pachinkos):
        throw
    if day == days:
        return 0
    if visited[pachinko]:
        return 0
    visited[pachinko] = true
    profit =
        matrix[day][pachinko] +
        (matrix, day+1, days, mod(pachinko-1, pachinkos), pachinkos, visited) +
        (matrix, day+1, days, mod(pachinko+1, pachinkos), pachinkos, visited)
    visited[pachinko] = false
    return profit

mod(i, n):
    m = i %n
    if m < n:
        m += n
    return m
Without backtracking:
int (matrix):
    if matrix == null || matrix.length() == 0 || matrix[0].length() == null:
        throw
    days = matrix.length()
    pachinkos = matrix[0].length()
    maxprofit = {value: null}
    for p = 0, p < pachinkos, p++:
        (matrix, days, pachinkos, maxprofit, d: 0, p: p)
    return maxprofit.value

(matrix, days, pachinkos, maxprofit, d, p,
    profit = 0, visited = bool[pachinkos]):
    if !(0 <= p < pachinkos):
        throw
    if !(0 <= d <= days):
        throw
    if d == days:
        if maxprofit.value == null || profit > maxprofit.value:
            maxprofit.value = profit
        return
    if visited[p]:
        return
    visited[p] = true
    profit += matrix[d][p]
    (matrix, days, pachinkos, maxprofit, d+1, mod(p-1, pachinkos), profit, visited)
    (matrix, days, pachinkos, maxprofit, d+1, mod(p+1, pachinkos), profit, visited)
    visited[p] = false

int mod(i, n):
    m = i %n
    if m < 0:
        m += n
    return m
[Hat tip to SM]

No comments:

Post a Comment