ナップサック問題で選んだ品物を表示させたい

ナップサック問題を解くコードをpythonで書いています。以下のコードはネットで調べたものをもとに作りました。

python
1#item[[weight,price],[].....]
2item = [[13,15],[23,30],[27,40],[33,60],[41,70],[45,80],[58,85],[60,90]]
3capacity = 100 
4
5#i番目以降のパッキングの価値の最大値
6def knapsack(i, capacity):
7    if i>=len(item):
8        return 0
9    elif  capacity - item[i][0] < 0.0:
10        return knapsack(i+1, capacity)
11    else:
12        #i番目の品物を入れない場合
13        p1 = knapsack(i+1, capacity)
14        
15        #i番目の品物を入れる場合
16        p2 = knapsack(i+1, capacity - item[i][0]) + item[i][1]
17        if p1>p2:
18            return p1
19        else:
20            return p2
21p = knapsack(0, capacity)
22
23print("TOTAL PRICE=",p)

このプログラムはcapacity内で買える組み合わせのうち最も高い金額が出力されますが、このプログラムを修正して最も高い金額になるときどの品物を買ったのかを出力するプログラムにしたいです。どのようにコードを修正すればいいのか教えてください。

行動規範の内容に同意します

回答1件

ベストアンサー

knapsack() 関数を改造し、戻り値として、現在選択されているアイテムのIndexのリストも戻すようにしてみました。
あとはそのIndex値に対応した品物名を表示すると良いのではないかと思います

Python
1# item[[weight,price],[].....]
2item = [[13, 15], [23, 30], [27, 40], [33, 60],
3        [41, 70], [45, 80], [58, 85], [60, 90]]
4name = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
5capacity = 100
6
7# i番目以降のパッキングの価値の最大値
8
9
10def knapsack(i, capacity):
11    if i >= len(item):
12        return 0, []
13    elif capacity - item[i][0] < 0.0:
14        return knapsack(i+1, capacity)
15    else:
16        # i番目の品物を入れない場合
17        p1, l1 = knapsack(i+1, capacity)
18
19        # i番目の品物を入れる場合
20        p2, l2 = knapsack(i+1, capacity - item[i][0])
21        p2 += item[i][1]
22        l2.append(i)
23        if p1 > p2:
24            return p1, l1
25        else:
26            return p2, l2
27
28
29price, lst = knapsack(0, capacity)
30
31print("TOTAL PRICE=", price)
32print("ITEMS : {}".format(','.join(name[i] for i in lst)))