Python Algorithme Glouton

Je suis en train d'écrire un algorithme glouton (Python 3.x.x) pour un bijou hold-up'. Étant donné une série de bijoux et de valeurs, le programme attrape le plus précieux joyau qu'il puisse tenir dans son sac sans passer sur le sac de limite de poids. J'ai trois cas de test ici, et il fonctionne parfaitement pour deux d'entre eux.

Chaque cas de test est écrit de la même manière: la première ligne est le sac de limite de poids, toutes les lignes suivantes sont des n-uplets(poids, valeur).

Exemple de Cas 1 (travaux):

10
3 4
2 3
1 1

Exemple de Cas 2 (ne fonctionne pas):

575
125 3000
50 100
500 6000
25 30

Code: 

def take_input(infile):
f_open = open(infile, 'r')
lines = []
for line in f_open:
lines.append(line.strip())
f_open.close()
return lines
def set_weight(weight):
bag_weight = weight
return bag_weight
def jewel_list(lines):
jewels = []
for item in lines:
jewels.append(item.split())
jewels = sorted(jewels, reverse= True)
jewel_dict = {}
for item in jewels:
jewel_dict[item[1]] = item[0]
return jewel_dict
def greedy_grab(weight_max, jewels):
#first, we get a list of values
values = []
weights = []
for keys in jewels:
weights.append(jewels[keys])
for item in jewels.keys():
values.append(item)
values = sorted(values, reverse= True)
#then, we start working
max = int(weight_max)
running = 0
i = 0
grabbed_list = []
string = ''
total_haul = 0
# pick the most valuable item first. Pick as many of them as you can.            
# Then, the next, all the way through.
while running < max:
next_add = int(jewels[values[i]])
if (running + next_add) > max:
i += 1
else:
running += next_add
grabbed_list.append(values[i])
for item in grabbed_list:
total_haul += int(item)
string = "The greedy approach would steal $" + str(total_haul) + " of  
jewels."
return string
infile = "JT_test2.txt"
lines = take_input(infile)
#set the bag weight with the first line from the input
bag_max = set_weight(lines[0])
#once we set bag weight, we don't need it anymore
lines.pop(0)
#generate a list of jewels in a dictionary by weight, value
value_list = jewel_list(lines)
#run the greedy approach
print(greedy_grab(bag_max, value_list))

Quelqu'un aurait-il des indices pourquoi ça ne marcherait pas pour le cas 2? Votre aide est grandement appréciée.
EDIT: Le résultat attendu pour le cas 2 $6130. Je semble pour obtenir $6090.

  • Qu'est-ce que la production prévue dans case2, et qu'est-ce que l'output observé pour case2?
  • Prévu: $6130 Réel: $6090
  • Vous devriez vraiment modifier cette information dans votre post, afin que chacun puisse voir. Aussi, qu'est-ce que le résultat observé?
  • Édité. Merci!
  • Aussi, s'il vous plaît corriger l'indentation dans votre code. Collez votre code, puis cliquez sur le {} bouton juste au-dessus de la zone de texte, de le faire.
  • Sonne comme le problème de sac-à-dos

InformationsquelleAutor idalsin | 2013-10-24
  1. 2

    Votre dictionnaire les clés sont des chaînes de caractères, pas des nombres entiers, de sorte qu'ils sont classés comme la chaîne lorsque vous essayez de les trier. Donc, vous obtiendrez:

    ['6000', '3000', '30', '100']

    au lieu recherché:

    ['6000', '3000', '100', '30']

    Modifier cette fonction pour être comme cela, et d'avoir entier clés:

    def jewel_list(lines):
jewels = []
for item in lines:
jewels.append(item.split())
jewels = sorted(jewels, reverse= True)
jewel_dict = {}
for item in jewels:
jewel_dict[int(item[1])] = item[0]  # changed line
return jewel_dict

    Lorsque vous modifiez ce qu'il va vous donner:

    The greedy approach would steal $6130 of jewels.
    InformationsquelleAutor iblazevic
  2. 1
    In [237]: %paste
def greedy(infilepath):
with open(infilepath) as infile:
capacity = int(infile.readline().strip())
items = [map(int, line.strip().split()) for line in infile]
bag = []
items.sort(key=operator.itemgetter(0))
while capacity and items:
if items[-1][0] <= capacity:
bag.append(items[-1])
capacity -= items[-1][0]
items.pop()
return bag
## -- End pasted text --
In [238]: sum(map(operator.itemgetter(1), greedy("JT_test1.txt")))
Out[238]: 8
In [239]: sum(map(operator.itemgetter(1), greedy("JT_test2.txt")))
Out[239]: 6130
    InformationsquelleAutor inspectorG4dget
  3. 0

    Je pense que dans ce morceau de code i doit être incrémenté sur l'autre côté trop

    while running < max:
next_add = int(jewels[values[i]])
if (running + next_add) > max:
i += 1
else:
running += next_add
grabbed_list.append(values[i])
i += 1 #here

    ce et @iblazevic la réponse explique pourquoi il se comporte de cette façon

    • Ne serait pas l'incrémentation sur la partie de la boucle while qu'il cesse d'être un algorithme glouton? Je veux garder la cueillette que de haute valeur bijou jusqu'à ce qu'il satisfait à la première instruction if, puis itérer passé à la suivante dans la liste. Je pense que votre façon serait seulement me permettre de reprendre le bijou une fois, si je suis correct.
    • oh, ok, je croyais que vous pouvez uniquement choisir, une fois
    • vous pourriez faire quelque chose comme running += (max-running) / value*value
    InformationsquelleAutor titus