5020 views

あらすじ

ここでみんな大好きな「動的計画法」を試してみる。
(ナップサック問題でググると、一番上に出てきたりします。)
何がすごいのか全然理解していないが、とりあえずやってみた。

動的計画法とは

別名：「DP(DynamicProgram)」
調べてみると、ちょっと複雑そうなので、違うページで練習する(違うページ：)

実装1

とりあえず、テーブルを作る前に、必要箇所だけ求める方式で作成する。
※今回は、各一つずつ詰め込み場合を想定している。例題と条件が違うけど、、、

コード


# ターゲットとなる容量
target = 65



# 重さと値段を保存するクラスを作成
class Item:
    def __init__(self, w=0, p=0):
        self.weight = w
        self.price = p


# 配列にして保存する。
items = [Item(10, 120), Item(12, 130), Item(7, 80),
         Item(9, 100), Item(21, 250), Item(16, 185)
         ]


# ナップサックの処理(一応DP)
def knapsack():
    # 初期値の設定
    weight = 0
    value = 0
    M_value = 0

    # 品の数だけ回す。
    for i in range(len(items)):
        j = i
        # 最初に使える品は1品のみ。少しずつ増やす
        while j >= 0:
            weight += items[j].weight

            # 重さがターゲット以下
            if weight <= target:
                value += items[j].price
            # 重さがターゲト以上
            else:
                weight -= items[j].weight

            j -= 1
        # 結果の出力
        print(value, ":", weight)

        # 今回求めた、値とこれまでの最大値を比較。値が少しでも高いほうをM_valueとする。
        if M_value < value:
            M_value = value

        # 初期化
        value = 0
        weight = 0

    return M_value


print(knapsack())

出力

お、いい感じ。

実装2

テーブルを使う場合を実装してみる
※複数個入れることができるパターンの場合

コード

# ターゲットとなる容量
target = 65



# 重さと値段を保存するクラスを作成
class Item:
    def __init__(self, w=0, p=0):
        self.weight = w
        self.price = p


# 配列にして保存する。
items = [Item(10, 120), Item(12, 130), Item(7, 80),
         Item(9, 100), Item(21, 250), Item(16, 185)
         ]

dp = [[[]for i in range(target+1)] for j in range(len(items)+1)]
memo = []


def serachNum(i,j):
    target = j
    num = i - 1
    # 現在の値
    weight = items[num].weight
    price = items[num].price

    while True:
        # ここの処理は変更していない。
        memo.append(weight)
        if weight == target:
            break
        elif target<weight:
            weight -= items[num].weight
            price -= items[num].price
            num -=1
            if num ==-1:
                break
            else:
                weight += items[num].weight
                price += items[num].price

        else:
            weight += items[num].weight
            price += items[num].price

    print("値:",price,"重さ：",weight,)


    return price





# ナップサックの処理(一応DP)
def knapsack():
    # 初期値の設定
    weight = 0
    value = 0
    M_value = 0

    for i in range(len(items)+1):
        for j in range(target+1):
            # 0行目
            if i == 0:

                if j == 0:
                    # 0列目
                    dp[i][j] = 0
                else:
                    dp[i][j] = "INF"

            else:
                if j == 0:
                    # 配列0列目
                    dp[i][j] = 0
                else:
                    # 配列1個目以降
                    # 一つ前のコインの組み合わせ方を取得
                    # 今回求めたコインの組み合わせを取得
                    comparison = dp[i - 1][j]
                    ans = serachNum(i, j)

                    if type(comparison) == int:
                        if ans > comparison:
                            # 今回の組み合わせが最短手だった時
                            dp[i][j] = ans
                        else:
                            # 前回以前の組み合わせが最短手だった時
                            dp[i][j] = comparison

                    else:
                        # 一つ前の最善手が数字ではないとき
                        dp[i][j] = ans


knapsack()

for i in dp:
    print(i)

出力

21, 250を3つ詰め込むのが最適解みたいですね,,,,

実装3

テーブルを使う場合を実装してみる
※1個入れることができるパターンの場合

コード

# ターゲットとなる容量
target = 65



# 重さと値段を保存するクラスを作成
class Item:
    def __init__(self, w=0, p=0):
        self.weight = w
        self.price = p


# 配列にして保存する。
items = [Item(10, 120), Item(12, 130), Item(7, 80),
         Item(9, 100), Item(21, 250), Item(16, 185)
         ]

dp = [[[]for i in range(target+1)] for j in range(len(items)+1)]
memo = []


def serachNum(i,j):
    target = j
    num = i - 1
    # 現在の値
    weight = items[num].weight
    price = items[num].price

    while True:
        # ここの処理は変更していない。
        memo.append(weight)
        if weight == target:
            break
        elif target<weight:
            weight -= items[num].weight
            price -= items[num].price
            num -= 1
            if num == -1:
                break
            else:
                weight += items[num].weight
                price += items[num].price
        else:
            num -=1
            if num == -1:
                break
            else:
                weight += items[num].weight
                price += items[num].price


    print("値:",price,"重さ：",weight,)


    return price





# ナップサックの処理(一応DP)
def knapsack():
    # 初期値の設定
    weight = 0
    value = 0
    M_value = 0

    for i in range(len(items)+1):
        for j in range(target+1):
            # 0行目
            if i == 0:

                if j == 0:
                    # 0列目
                    dp[i][j] = 0
                else:
                    dp[i][j] = "INF"

            else:
                if j == 0:
                    # 配列0列目
                    dp[i][j] = 0
                else:
                    # 配列1個目以降
                    # 一つ前のコインの組み合わせ方を取得
                    # 今回求めたコインの組み合わせを取得
                    comparison = dp[i - 1][j]
                    ans = serachNum(i, j)

                    if type(comparison) == int:
                        if ans > comparison:
                            # 今回の組み合わせが最短手だった時
                            dp[i][j] = ans
                        else:
                            # 前回以前の組み合わせが最短手だった時
                            dp[i][j] = comparison

                    else:
                        # 一つ前の最善手が数字ではないとき
                        dp[i][j] = ans


knapsack()