Python ナップザック問題を貪欲法( greedy algorithm)で解く

ナップサック問題 (Wikipedia) を 貪欲法 (Wikipedia) で解きます。貪欲法で求められる解は厳密解とは限らないので注意が必要です。
コードに関して不備や改良案等があればご教示頂けますと幸いです。

(貪欲法についてWikipediaより)

以下にナップサック問題での適用例を示す。この問題の場合は各荷物ごとに分割して評価することで適用可能である。
ナップサック問題の各荷物の評価値を決定する。（価値）÷（容積）という数字がよく使われる。
評価値の一番高い荷物を選ぶ。
その荷物をナップサックに入れても最大容量を越えないならナップサックに入れる。
全ての荷物を評価値の順に選び上記の操作を繰り返す。
なお、この問題に関しては貪欲法では最適解を得られない。

容積あたりの価値を計算してお得な荷物から詰めていく感じですね！

問題

4*x1 + 5*x2 + x3 + 3*x4 <= 6
xi = 0 or 1 (i = 1, 2, 3, 4)

上記条件の下で
7*x1 + 8*x2 + x3 + 2*x4
を最大にする( x1, x2, x3, x4 )を貪欲法を用いて求めよ。

解答

import numpy as np
from pandas import DataFrame

# 制約条件より
weights = np.array([4, 5, 1, 3])
# 目的関数より
values = np.array([7, 8, 1, 2])
# xの配列。初期値はすべて0とする。採択した時に1にする。
results = np.array([0, 0, 0, 0])
# 評価値を算出。
evaluates = values/weights
# DataFrameにまとめる
target_df = DataFrame(np.c_[evaluates, weights, values, results], index=['x1', 'x2', 'x3', 'x4'], columns = ['evaluate', 'weight', 'value', 'result'])
# evaluateの値で降順に並び替える
target_df.sort_values('evaluate', ascending=False)

# 採択した項目のweightの和。初期値0。
weight_sum = 0

# 評価値の高いものからループを回す
for index, target in target_df.iterrows():
    # 制約条件をクリアしたら採択
    if weight_sum + target['weight'] <= 6:
        weight_sum += target['weight']
        target['result'] = 1
        
print(target_df)
print("---answer---")
print(target_df['result'])

sort

DataFrameのsortは sort_valuesで出来ました。sortでやろうとしたらDEPRECATEDが出ました。
ascending で逆順に並びます。
pandas.DataFrame.sort

numpyだけで逆順ソートをやろうとすると以下のようにして出来ました。

import numpy as np
arr = np.array([[4, 2], [5, 2], [6, 4], [1, 3], [2, 3]])
arr = arr[ arr[:,0].argsort() ] # 0番目でsort
arr = arr[::-1]
print(arr)

[[6 4]
 [5 2]
 [4 2]
 [2 3]
 [1 3]]

少し面倒くさい。。

結果

    evaluate  weight  value  result
x1  1.750000     4.0    7.0     1.0
x2  1.600000     5.0    8.0     0.0
x3  1.000000     1.0    1.0     1.0
x4  0.666667     3.0    2.0     0.0
---answer---
x1    1.0
x2    0.0
x3    1.0
x4    0.0
Name: result, dtype: float64

よって、
( x1, x2, x3, x4 ) = ( 1, 0, 1, 0 )