Animate the basics of dynamic programming and the knapsack problem
Unlimited number knapsack problem
Algorithm for solving the unlimited number knapsack problem by dynamic programming
def knapsack02(x, W, V):
for i in range(len(W)):
for j in range(x + 1):
if j < W[i]:
dp_table[i + 1][j] = dp_table[i][j]
else:
dp_table[i + 1][j] = max(dp_table[i][j], dp_table[i + 1][j - W[i]] + V[i])
movie.append(draw02(dp_table, i, j))
return dp_table[len(W)][x]
Animation drawing
def draw02(dp_table, i, j):
image = []
if i == 0 and j == 0:
im_text = plt.text(0, weight_limit * 1.1, "Start!", size=20)
image.append(im_text)
elif i == len(V) - 1 and j == weight_limit:
im_text = plt.text(0, weight_limit * 1.1, "Finish!", size=20)
image.append(im_text)
elif i >= 0:
im_text = plt.text(0, weight_limit * 1.1,
"Item " + str(i) + ": (V,W)=(" + str(V[i]) + ", " + str(W[i]) + ")" , size=20)
image.append(im_text)
for w in range(weight_limit + 1):
if j == w:
w_lmt = plt.plot(-1, w, markersize=16, marker="$" + str(w) + "$", c="black")
else:
w_lmt = plt.plot(-1, w, markersize=12, marker="$" + str(w) + "$", c="gray")
image += w_lmt
for v in range(len(V) + 1):
if v < len(V):
if i == v:
item_vw = plt.plot(v + 1, -1, markersize=22, marker="$" + str(V[v]) + "," + str(W[v]) + "$", c="black")
image += item_vw
item_id = plt.plot(v + 1, -2, markersize=16, marker="$" + str(v) + "$", c="black")
image += item_id
else:
item_vw = plt.plot(v + 1, -1, markersize=20, marker="$" + str(V[v]) + "," + str(W[v]) + "$", c="gray")
image += item_vw
item_id = plt.plot(v + 1, -2, markersize=12, marker="$" + str(v) + "$", c="gray")
image += item_id
else:
vw = plt.plot(0, -1, markersize=20, marker="$V,W$", c="gray")
image += vw
for w in range(weight_limit + 1):
if v == i and w == j:
color="black"
elif v == i + 1 and w == j:
color="red"
elif dp_table[v][w] == 0:
color="lightgray"
else:
color="blue"
square = plt.plot(v, w, markersize=40, marker="s", c="lightblue", alpha=0.5)
image += square
numeral = plt.plot(v, w, markersize=20, marker="$" + str(dp_table[v][w]) + "$", c=color)
image += numeral
image.append(plt.ylabel("Weight limit j", size=20))
image.append(plt.xlabel("Items i", size=20))
return image
Execution example 1
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML
movie = []
weight_limit = 9
W = [5, 2, 1]
V = [9, 5, 2]
n = len(W)
fig = plt.figure(figsize=(10, 10))
dp_table = [[0 for _ in range(weight_limit + 1)] for _ in range(len(W) + 1)]
movie.append(draw02(dp_table, -1, -1))
knapsack02(weight_limit, W, V)
ani = animation.ArtistAnimation(fig, movie, interval=1000, repeat_delay=1000)
ani.save("knapsack02-1.gif", writer='pillow')
HTML(ani.to_jshtml())
- If the animation ends and stops, you can move it again by clicking the image.
Execution example 2
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML
movie = []
weight_limit = 8
W = [5, 6, 2, 1, 3]
V = [8, 9, 5, 1, 7]
n = len(W)
fig = plt.figure(figsize=(10, 10))
dp_table = [[0 for _ in range(weight_limit + 1)] for _ in range(len(W) + 1)]
movie.append(draw02(dp_table, -1, -1))
knapsack02(weight_limit, W, V)
ani = animation.ArtistAnimation(fig, movie, interval=1000, repeat_delay=1000)
ani.save("knapsack02-2.gif", writer='pillow')
HTML(ani.to_jshtml())
- If the animation ends and stops, you can move it again by clicking the image.
String matching
def stringmatch(s, t):
movie.append(draw_s(dp_table, -1, -1))
for i in range(len(s)):
for j in range(len(t)):
if s[i] == t[j]:
dp_table[i + 1][j + 1] = dp_table[i][j] + 1
else:
dp_table[i + 1][j + 1] = max(dp_table[i][j + 1], dp_table[i + 1][j])
movie.append(draw_s(dp_table, i, j))
return dp_table[len(s)][len(t)]
Animation drawing
def draw_s(dp_table, i, j):
image = []
for w in range(len(t)):
if j == w:
w_lmt = plt.plot(-1, w + 1, markersize=16, marker="$" + t[w] + "$", c="black")
else:
w_lmt = plt.plot(-1, w + 1, markersize=12, marker="$" + t[w] + "$", c="gray")
image += w_lmt
for v in range(len(s) + 1):
if v < len(s):
if i == v:
item_vw = plt.plot(v + 1, -1, markersize=22, marker="$" + s[v] + "$", c="black")
image += item_vw
else:
item_vw = plt.plot(v + 1, -1, markersize=20, marker="$" + s[v] + "$", c="gray")
image += item_vw
for w in range(len(t) + 1):
if v >= 1 and w >= 1 and s[v - 1] == t[w - 1]:
color = "orange"
else:
color = "lightblue"
square = plt.plot(v, w, markersize=40, marker="s", c=color, alpha=0.5)
image += square
if v == i and w == j:
color="black"
elif v == i and w == j + 1:
color="black"
elif v == i + 1 and w == j:
color="black"
elif v == i + 1 and w == j + 1:
color="red"
elif dp_table[v][w] == 0:
color="lightgray"
else:
color="blue"
numeral = plt.plot(v, w, markersize=20, marker="$" + str(dp_table[v][w]) + "$", c=color)
image += numeral
return image
Execution example 1
s = "PENCILS"
t = "PENGUINS"
fig = plt.figure(figsize=(10, 10))
movie = []
dp_table = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
stringmatch(s, t)
ani = animation.ArtistAnimation(fig, movie, interval=500, repeat_delay=1000)
ani.save("knapsack_s-1.gif", writer='pillow')
HTML(ani.to_jshtml())
- If the animation ends and stops, you can move it again by clicking the image.
0-1 knapsack problem
def knapsack01(i, j):
movie.append(draw01(dp_table, i, j))
if dp_table[i][j] >= 0:
return dp_table[i][j]
if j == 0:
ret = 0
elif i == n:
ret = 0
else:
dp_table[i ][j] = -2
if W[i] > j:
ret = knapsack01(i + 1, j)
else:
ret = max(knapsack01(i + 1, j), knapsack01(i + 1, j - W[i]) + V[i])
dp_table[i][j] = ret
movie.append(draw01(dp_table, i, j))
return ret
Animation drawing
def draw01(dp_table, i, j):
image = []
if i > 0:
if W[i - 1] <= j:
arrow = " <= "
else:
arrow = " > "
im_text = plt.text(0, weight_limit * 1.2,
"Item " + str(i) + ": (V,W)=(" + str(V[i - 1]) + ", " + str(W[i - 1]) + ")" , size=20)
image.append(im_text)
else:
if dp_table[i][j] == -1:
im_text = plt.text(0, weight_limit * 1.2, "Start!", size=20)
image.append(im_text)
else:
im_text = plt.text(0, weight_limit * 1.2, "Finish!", size=20)
image.append(im_text)
for w in range(weight_limit + 1):
if j == w:
w_lmt = plt.plot(-1, w, markersize=16, marker="$" + str(w) + "$", c="black")
else:
w_lmt = plt.plot(-1, w, markersize=12, marker="$" + str(w) + "$", c="gray")
image += w_lmt
for v in range(len(V) + 1):
if v < len(V):
if i == v + 1:
item_vw = plt.plot(v + 1, -1, markersize=22, marker="$" + str(V[v]) + "," + str(W[v]) + "$", c="black")
image += item_vw
item_id = plt.plot(v + 1, -2, markersize=16, marker="$" + str(v) + "$", c="black")
image += item_id
else:
item_vw = plt.plot(v + 1, -1, markersize=20, marker="$" + str(V[v]) + "," + str(W[v]) + "$", c="gray")
image += item_vw
item_id = plt.plot(v + 1, -2, markersize=12, marker="$" + str(v) + "$", c="gray")
image += item_id
else:
vw = plt.plot(0, -1, markersize=20, marker="$V,W$", c="gray")
image += vw
for w in range(weight_limit + 1):
if v == i and w == j:
color="red"
elif dp_table[v][w] == -1:
color="lightgray"
else:
color="blue"
square = plt.plot(v, w, markersize=50, marker="s", c="lightblue", alpha=0.5)
image += square
numeral = plt.plot(v, w, markersize=20, marker="$" + str(dp_table[v][w]) + "$", c=color)
image += numeral
image.append(plt.ylabel("Weight limit j", size=20))
image.append(plt.xlabel("Items i", size=20))
return image
Execution example 1
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML
movie = []
weight_limit = 3
W = [5, 2, 3, 2, 1]
V = [9, 5, 6, 3, 2]
n = len(W)
fig = plt.figure(figsize=(14, 7))
dp_table = [[-1 for _ in range(weight_limit + 1)] for _ in range(len(W) + 1)]
movie.append(draw01(dp_table, -1, -1))
knapsack01(0, weight_limit)
ani = animation.ArtistAnimation(fig, movie, interval=2000, repeat_delay=1000)
ani.save("knapsack01-1.gif", writer='pillow')
HTML(ani.to_jshtml())
- If the animation ends and stops, you can move it again by clicking the image.
Execution example 2
import random
import matplotlib.pyplot as plt
import matplotlib.animation as animation
from IPython.display import HTML
movie = []
weight_limit = 5
W = [2, 4, 5, 1, 3, 6, 2]
V = [2, 1, 5, 1, 5, 9, 1]
n = len(W)
fig = plt.figure(figsize=(14, 8))
dp_table = [[-1 for _ in range(weight_limit + 1)] for _ in range(len(W) + 1)]
movie.append(draw01(dp_table, -1, -1))
knapsack01(0, weight_limit)
ani = animation.ArtistAnimation(fig, movie, interval=2000, repeat_delay=1000)
ani.save("knapsack01-2.gif", writer='pillow')
HTML(ani.to_jshtml())
- If the animation ends and stops, you can move it again by clicking the image.
Recommended Posts