2020-01-16 python递归实现最小cost问题

#!/usr/bin/python

“””

Author: zhiwen Wang

date: 2020.1.16

“””

import os

import sys

import numpy as np

def Minimum_cost_(profit_matrix, rows, cols):

    if len(rows) == 1 or len(cols) == 1:

        min_value = profit_matrix[rows,cols].min()

        idx = profit_matrix[rows,cols].argmin()

        if len(rows) == 1:

            return min_value,np.hstack((rows, cols[idx]))

        else:

            return min_value,np.hstack((rows[idx], cols))

    min_value, min_index = Minimum_cost_(profit_matrix, rows[1:], cols[1:])

    min_value += profit_matrix[rows[0],cols[0]]

    min_index = np.vstack((np.hstack((rows[0],cols[0])), min_index))

    for i in range(cols.shape[0]):

        if i==0: continue

        temp_min_value, temp_min_index = Minimum_cost_(profit_matrix, np.delete(rows,0), np.delete(cols,i))

        temp_min_value += profit_matrix[rows[0], cols[i]]

        if temp_min_value < min_value:

            min_value = temp_min_value

            min_index = np.vstack((np.hstack((rows[0],cols[i])), temp_min_index))

    return min_value, min_index

def Minimum_cost(profit_matrix):

    if type(profit_matrix) == list:

        profit_matrix = np.array(profit_matrix, dtype=float)

    rows, cols = np.arange(profit_matrix.shape[0],dtype=int), np.arange(profit_matrix.shape[1],dtype=int)

    cost, indexs = Minimum_cost_(profit_matrix, rows, cols)

    return cost, indexs

if __name__ == ‘__main__’:

    profit_matrix = [

        [62, 75, 80, 93, 95, 97],

        [75, 80, 82, 85, 71, 97],

        [80, 75, 81, 98, 90, 97],

        [78, 82, 84, 80, 50, 98],

        [90, 85, 85, 80, 85, 99],

        [65, 75, 80, 75, 68, 96]]

    print(“Expected results:\n\t[(0, 0), (1, 2), (2, 1), (3, 4), (4, 5), (5, 3)]”)

    print(“Results:\n\t”)

    cost, indexs = Minimum_cost(profit_matrix)

    print(cost,”\n\r”, indexs)

https://www.jianshu.com/p/ed886626a559

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论