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

Recommended Posts

A memo that solves the knapsack problem by the greedy algorithm
Solving the Python knapsack problem with the greedy algorithm
Let's make a robot that solves the Rubik's Cube! 2 Algorithm
A memo that I touched the Datastore with python
Finding a solution to the N-Queen problem with a genetic algorithm (2)
Let's make a robot that solves the Rubik's Cube! 3 Software
Let's make a robot that solves the Rubik's Cube! 1 Overview
Finding a solution to the N-Queen problem with a genetic algorithm (1)
A memo that reproduces the slide show (gadget) of Windows 7 on Windows 10.
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
I made a program that solves the spot the difference in seconds
Solve the Python knapsack problem with a branch and bound method
A class that freely changes the PLC value by socket communication
Illustration of the results of the knapsack problem
A memo organized by renaming the file names in the folder with python
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
A class that hits the DMM API
Search the maze with the python A * algorithm
AtCoderBeginnerContest154 Participation memo (Python, A ~ E problem)
Write a simple greedy algorithm in Python
We will implement the optimization algorithm (Problem)
A code that corrects the yoon / sokuon (sokuon)
[Python] A program that rounds the score
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
Try to solve the traveling salesman problem with a genetic algorithm (execution result)
Solution to the problem that you can't activate by putting conda in pyenv
[Python] Solution to the problem that elements are linked when copying a list