動的計画法とナップサック問題の基礎をアニメーションで

個数制限なしナップサック問題

個数制限なしナップサック問題を動的計画法で解くアルゴリズム

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]

アニメーション描画

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

実行例１

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()) 

※ アニメーションが終了し停止してしまった場合、画像をクリックするともう一度動かせると思います。

実行例２

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()) 

※ アニメーションが終了し停止してしまった場合、画像をクリックするともう一度動かせると思います。

文字列マッチング

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)]

アニメーション描画

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

実行例１

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()) 

※ アニメーションが終了し停止してしまった場合、画像をクリックするともう一度動かせると思います。

0-1ナップサック問題

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

アニメーション描画

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

実行例１

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()) 

※ アニメーションが終了し停止してしまった場合、画像をクリックするともう一度動かせると思います。

実行例２

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()) 

※ アニメーションが終了し停止してしまった場合、画像をクリックするともう一度動かせると思います。