Résolvez le problème du sac à dos Python avec l'algorithme glouton

[Problème de sac à dos (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) Résoudre avec% B2% E6% B3% 95). Notez que la solution requise par la méthode gloutonne n'est pas toujours une solution exacte. Nous vous serions reconnaissants si vous pouviez nous faire savoir s'il y a des lacunes ou des suggestions d'amélioration concernant le code.

(À propos de la méthode de cupidité de Wikipedia)

Un exemple d'application au problème du sac à dos est présenté ci-dessous. Dans le cas de ce problème, il peut être appliqué en divisant et en évaluant chaque bagage.
Déterminez la valeur de chaque bagage dans le problème du sac à dos. Le nombre (valeur) ÷ (volume) est souvent utilisé.
Sélectionnez le bagage avec la valeur d'évaluation la plus élevée.
Si le bagage ne dépasse pas la capacité maximale même si vous le mettez dans le sac à dos, mettez-le dans le sac à dos.
Sélectionnez tous les bagages dans l'ordre de la valeur d'évaluation et répétez l'opération ci-dessus.
La solution optimale ne peut pas être obtenue par la méthode gourmande pour ce problème.

C'est comme calculer la valeur par volume et emballer à partir d'une bonne affaire!

problème

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

Dans les conditions ci-dessus
7*x1 + 8*x2 + x3 + 2*x4
Pour maximiser( x1, x2, x3, x4 )Utilisez la méthode gourmande.

répondre

import numpy as np
from pandas import DataFrame

#Des contraintes
weights = np.array([4, 5, 1, 3])
#De la fonction objectif
values = np.array([7, 8, 1, 2])
#Un tableau de x. La valeur initiale est tout 0. Défini sur 1 une fois adopté.
results = np.array([0, 0, 0, 0])
#Calculez la valeur d'évaluation.
evaluates = values/weights
#Assembler dans un DataFrame
target_df = DataFrame(np.c_[evaluates, weights, values, results], index=['x1', 'x2', 'x3', 'x4'], columns = ['evaluate', 'weight', 'value', 'result'])
#Trier par ordre décroissant par valeur d'évaluation
target_df.sort_values('evaluate', ascending=False)

#La somme des poids des éléments adoptés. Valeur initiale 0.
weight_sum = 0

#Tournez la boucle de celle avec la valeur d'évaluation la plus élevée
for index, target in target_df.iterrows():
    #Adopté après élimination des contraintes
    if weight_sum + target['weight'] <= 6:
        weight_sum += target['weight']
        target['result'] = 1
        
print(target_df)
print("---answer---")
print(target_df['result'])

sort Le tri DataFrame était composé de sort_values. Quand j'ai essayé de le faire avec sort, je suis devenu DEPRECATED. Disposer dans l'ordre inverse avec «ascendant». pandas.DataFrame.sort

Lorsque j'ai essayé de trier dans l'ordre inverse uniquement avec numpy, cela a été fait comme suit.

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

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

C'est un peu ennuyeux. ..

résultat

    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

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