2

私がこれを持っているとしましょう：

1A=6 2A=4.5  3A=6

1B=7 2B=6    3B=7.5

1C=6 2C=6.75 3C=9

合計が最大になる数字の組み合わせを見つけたいです。文字の前の数字は 1 回しか使用できず、数字の後の文字は 1 回しか使用できません。例えば。1A+2B+3C, 1C+2B+3A有効です。1A+1B+2B,3A+2B+3B,1A+2A+3Aは無効です。

この場合、最高額は1A+2B+3C=21です。Pythonを使用してこの結果と組み合わせを見つけるにはどうすればよいですか?

前もって感謝します

4

4 に答える 4

2

私は Python 派ではないので、次のコードは「Python スタイル」ではないように見えるかもしれませんが、アルゴリズムは問題ないはずです。

#test input. the matrix can be any n * n size.
matrix = [[6,7,6],[4.5,6,6.75],[6,7.5,9]]

#assistant array to track which numbers we have already used.
#check[i] = 1 if i has been used
check = [0]* len(matrix)

#max sum
max_sum = 0

def getMax(matrix,check,row,curr_sum):
    global max_sum
    #base case, we have reached the last letter.
    #check to see if this combination is max
    if(row==len(matrix)-1):
        for i in range(len(check)):
            if(check[i]==0 and (matrix[row][i]+curr_sum)>max_sum):
                max_sum = matrix[row][i]+curr_sum
    #recursive case, pick the current available number, go to next letter.
    else:
        for i in range(len(check)):
            if(check[i]==0):
                check[i]=1
                getMax(matrix,check,row+1,curr_sum+matrix[row][i])
                check[i]=0

getMax(matrix,check,0,0)

print max_sum

これは、再帰を使用した一種のブルート フォース アルゴリズムであることに注意してください。時間の複雑さに関しては、より優れたアルゴリズム (動的計画法のアプローチなど) が存在します。メソッドにキャッシュを追加して、効率を向上させることができます。

また、組み合わせを知りたい場合は、組み合わせを追跡するための特別な努力が必要です。(例: 別のマトリックスを使用して記録する)

于 2013-05-07T05:50:27.043 に答える