Solving the Python knapsack problem with the greedy algorithm

[Knapsack Problem (Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83 % E3% 82% AF% E5% 95% 8F% E9% A1% 8C) Greedy Method (Wikipedia) Solve with% B2% E6% B3% 95). Note that the solution obtained by the greedy algorithm is not always an exact solution. We would appreciate it if you could let us know if there are any deficiencies or suggestions for improvement regarding the code.

(About greedy algorithm from Wikipedia)

An example of application to the knapsack problem is shown below. In the case of this problem, it can be applied by dividing and evaluating each package.
Determine the valuation of each package in the knapsack problem. The number (value) ÷ (volume) is often used.
Select the package with the highest evaluation value.
If the baggage does not exceed the maximum capacity even if you put it in the knapsack, put it in the knapsack.
Select all packages in order of evaluation value and repeat the above operation.
The optimal solution cannot be obtained by the greedy algorithm for this problem.

It's like calculating the value per volume and packing from a great deal!

problem

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

Under the above conditions
7*x1 + 8*x2 + x3 + 2*x4
To maximize( x1, x2, x3, x4 )Use the greedy algorithm.

answer

import numpy as np
from pandas import DataFrame

#From constraints
weights = np.array([4, 5, 1, 3])
#From the objective function
values = np.array([7, 8, 1, 2])
#An array of x. The initial value is all 0. Set to 1 when adopted.
results = np.array([0, 0, 0, 0])
#Calculate the evaluation value.
evaluates = values/weights
#Put together in a DataFrame
target_df = DataFrame(np.c_[evaluates, weights, values, results], index=['x1', 'x2', 'x3', 'x4'], columns = ['evaluate', 'weight', 'value', 'result'])
#Sort in descending order by value of evaluate
target_df.sort_values('evaluate', ascending=False)

#The sum of the weights of the adopted items. Initial value 0.
weight_sum = 0

#Turn the loop from the one with the highest evaluation value
for index, target in target_df.iterrows():
    #Adopted after clearing the constraints
    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 is made up of sort_values. When I tried to do it with sort, I got DEPRECATED. Arrange in reverse order with ʻascending`. pandas.DataFrame.sort

When I tried to sort in reverse order only with numpy, it was done as follows.

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

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

It's a little annoying. ..

result

    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

Therefore, ( x1, x2, x3, x4 ) = ( 1, 0, 1, 0 )