[PYTHON] A memo that solves the knapsack problem by the greedy algorithm

This is a memo when solving the knapsack problem by the greedy algorithm.

Greedy algorithm policy

Put the ones with high value per volume in the knapsack first, and the ones that are completely filled are the solution! That is the policy in the greedy algorithm of the knapsack problem. For example, in preparation for a harsh survival, if you can pack as many "horse 〇 sticks" and "〇 bottle satisfaction bars" that both have almost the same volume into knapsacks as you like, you can fill up the knapsacks Only the "book satisfaction bar" will be packed. It's based on that heuristic.

Notes on implementation

I personally find it convenient to assign one tuple (item, value, volume) to one item and keep it in a list. In other words, the list looks like this:

tuples = [ (Goods, value, volume), (Goods, value, volume), 　　　 : (Goods, value, volume) ]

When accessing the elements of a tuple in a list, for example

** "Volume" of item "3" **

When accessing

tuples[2][2]

You can get the value with.

code

knapsack_greedy.py

import numpy as np

C = 2             #Knapsack size
len = 10          #Number of items
tuples = []       #(Index, value, weight, value/List to hold weight)

#Greedy algorithm solution and its initialization
sol = np.zeros(10)

#Initialization of value and weight
values = np.random.rand(len)
costs = np.random.rand(len)


#(Index, value, volume, value/volume)
for i in range(len):
    tuples.append((i,values[i],costs[i],float(values[i]/costs[i])))

#Tuple after sorting
tuples_sorted = []
    
#value/Sort by volume
for x,y,z,w in sorted(tuples,key=lambda x:x[3],reverse = True):
    tuples_sorted.append((x,y,z,w))

sum = 0         #Variable for assignment

for i in range(len):
    #Put the items with the highest value per volume into the knapsack.
    sum+=tuples_sorted[i][2]
    if(sum < C):
        sol[tuples_sorted[i][0]]=1         #Insert if the capacity is not exceeded
    else:
        sol[tuples_sorted[i][0]]=0         #I can't put it in because it exceeds the capacity

print("Knapsack size"+str(C))
print("value")
print(np.round(values,3))
print("weight")
print(np.round(costs,3))
print("Selected item")
print(sol)

sum_ = 0
for i in range(len):
    sum_ += sol[i]*costs[i]
    
print("Total capacity of the selected item")
print(str(sum_))

output

Knapsack size 2
value
[ 0.631  0.543  0.668  0.337  0.011  0.454  0.536  0.527  0.434  0.833]
weight
[ 0.823  0.546  0.759  0.028  0.005  0.638  0.694  0.468  0.474  0.351]
Selected item
[ 0.  1.  0.  1.  1.  0.  0.  1.  1.  1.]
Total capacity of the selected item
1.87266067297