knapsack.py

from random import randrange
import matplotlib.pyplot as plt
from tqdm import tqdm
from time import time

def main():
    n = 10000
    par = 100
    res = []
    times = []
    n_set = list(range(1, n, par))
    for N in tqdm(n_set):
        # N = 50 # 商品の個数
        W = 1000 # ナップサックの容量
        MV = 100 # 価値の上限
        MW = 100 # 容量の上限
        k1, k2, time = knapsack(N, W, MV, MW)
        res.append((k1, k2))
        times.append(time)

    plt.scatter(n_set, [i for i, j in res], label='greedy1', color='blue')
    plt.scatter(n_set, [j for i, j in res], label='greedy2', color='green')
    plt.legend(loc='best')
    plt.xlabel('number of items')
    plt.ylabel('appro ratio')
    plt.title('W={}, MW={}'.format(W, MW))
    plt.grid()
    plt.savefig('sample.png')

    plt.clf()
    plt.scatter(n_set, [i for i, j, k in times], label='dynamic', color='orange')
    plt.scatter(n_set, [j for i, j, k in times], label='greedy1', color='blue')
    plt.scatter(n_set, [k for i, j, k in times], label='greedy2', color='green')
    plt.xlabel('number of items')
    plt.ylabel('time')
    plt.legend(loc='best')
    plt.title('computation time')
    plt.grid()
    plt.savefig('tmp.png')




def knapsack(N, W, MV, MW):
    v = [randrange(1, MV) for _ in range(N)]
    w = [randrange(1, MW) for _ in range(N)]

    # 動的計画法
    stime = time()
    dynamic_tv = dynamic_programming(N, W, v, w)
    dynamic_time = time() - stime
    # 貪欲法1
    stime = time()
    greedy1_tv = greedy1_programming(N, W, v, w)
    greedy1_time = time() - stime
    # 貪欲法2
    stime = time()
    greedy2_tv = greedy2_programming(N, W, v, w)
    greedy2_time = time() - stime

    # 結果の表示
    # print('dynamic', dynamic_tv)
    # print('greedy1', greedy1_tv, greedy1_tv/dynamic_tv)
    # print('greedy2', greedy2_tv, greedy2_tv/dynamic_tv)

    return greedy1_tv/dynamic_tv, greedy2_tv/dynamic_tv, (dynamic_time, greedy1_time, greedy2_time)


def dynamic_programming(N, W, v, w):
    # table[i][j] 商品1~i ナップサックの容量jでの最適値
    table = [[0 for i in range(W+1)] for j in range(N)]

    for i in range(N):
        for j in range(W+1):
            if i == 0:
                if w[i] <= j:
                    table[i][j] = v[i]
            elif w[i] > j:
                table[i][j] = table[i-1][j]
            else:
                table[i][j] = max(table[i-1][j], table[i-1][j-w[i]] + v[i])

    return table[N-1][W]


def greedy1_programming(N, W, v, w):
    sum_w = 0
    sum_v = 0
    sorted_i = sorted(range(N), key=lambda i: -v[i] / w[i])
    for i in sorted_i:
        if sum_w + w[i] > W:
            return max(sum_v, v[i])
        else:
            sum_w = sum_w + w[i]
            sum_v = sum_v + v[i]

    if sum_w > W:
        return sum_v - v[sorted_i[-1]]
    else:
        return sum_v


def greedy2_programming(N, W, v, w):
    sum_w = 0
    sum_v = 0
    sum_u = 0
    S = set()
    for _ in range(N):
        if sum_w > W:
            return sum_u
        else:
            sum_u = sum_v
            k = max(set(range(N))-S, key=lambda i: (sum_v + v[i]) / w[i])
            S.add(k)
            sum_w = sum_w + w[k]
            sum_v = sum_v + v[k]

    if sum_w > W:
        return sum_u
    else:
        return sum_v


if __name__ == '__main__':
    main()