ナップサック問題を解く

items = ((2,3),(1,2),(3,6),(2,1),(1,3),(5,85))
MAX_WEIGHT=4

1. 動的計画法

DPテーブルからアイテムの組み合わせを求める方法はこの本の記述を参考にした。
books.google.co.ke

#!/usr/bin/env python
import numpy as np
np.set_printoptions(linewidth=100)

wvs = [(2,3),(1,2),(3,6),(2,1),(1,3),(5,85)]
n = len(wvs)
W = sum([wv[0] for wv in wvs])
dp = np.zeros((n+1,W+1))

for i in range(1,n+1):
    for w in range(W+1):
        if(w-wvs[i-1][0]>=0):
            dp[i][w] = max(dp[i][w],dp[i-1][w-wvs[i-1][0]]+wvs[i-1][1])
        dp[i][w]  = max(dp[i][w],dp[i-1][w])

print(dp)

# calculation of the combination of items
MAX_WEIGHT=4
ans = max([d[MAX_WEIGHT] for d in dp])
dp2 = dp[:,:MAX_WEIGHT+1]
m, n = np.shape(dp2)
last = dp2[m-1,n-1]
taken = [0]*(m-1)
j = n-1
i = m-1
#print(dp2)
while j > 0 and i > 0:
    i -= 1
    cur = dp2[i,j]

    if last-cur > 0:
        taken[i] = 1
        j = j - wvs[i][0]
        last = dp2[i][j] 
        continue

print("given weight:",MAX_WEIGHT)
print("combination:",taken)
print("maximum value:",ans)

2. 遺伝的アルゴリズム（DEAP）

この本を参考にした。
https://www.amazon.co.jp/dp/B094993THZ/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1

from deap import base, creator, tools, algorithms
import random
import numpy as np

#items = ((8,10),(7,13),(6,7),(5,4),(4,9),(3,3,),(2,3),(1,2))
items = ((2,3),(1,2),(3,6),(2,1),(1,3),(5,85))

creator.create("Fitness", base.Fitness, weights=(1.0,))
creator.create("Individual",list,fitness=creator.Fitness)

toolbox = base.Toolbox()
toolbox.register("attribute",random.randint, 0, 1)
toolbox.register("individual",tools.initRepeat,creator.Individual,toolbox.attribute, len(items))
toolbox.register("population",tools.initRepeat,list,toolbox.individual)

#MAX_WEIGHT=10
MAX_WEIGHT=4
def evalKnapsack(individual):
    weight = 0.0
    value = 0.0
    for i in range(len(items)):
        s = individual[i]
        if s==1:
            weight += items[i][0]
            value += items[i][1]
    if weight > MAX_WEIGHT:
        return 0,

    return value,

toolbox.register("evaluate",evalKnapsack)
toolbox.register("select",tools.selTournament,tournsize=3)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate",tools.mutFlipBit, indpb=0.05)

hof = tools.ParetoFront()
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg",np.mean, axis=0)
stats.register("std",np.std, axis=0)
stats.register("min",np.min, axis=0)
stats.register("max",np.max, axis=0)

pop = toolbox.population(n=50)
algorithms.eaSimple(pop, toolbox, cxpb=0.8,mutpb=0.5,ngen=100,stats=stats,halloffame=hof, verbose=True)

best_ind = tools.selBest(pop,1)[0]
print(best_ind)
print(evalKnapsack(best_ind))

3. 線形計画問題（PuLP）

ここを参考に。
dev2prod.site

from pulp import *

#w = [4,2,2,1,10]
#v = [12,2,1,1,4]
#W = 15
w = [4,2,2,1,10]
v = [12,2,1,1,4]
W = 15
r = range(len(w))

m = LpProblem(sense=LpMaximize)
x = [LpVariable('x%d'%i, cat=LpBinary) for i in r]

m += lpDot(v,x)
m += lpDot(w,x) <= W
m.solve()

print('max value: {} / combination:{}'.format(
    value(m.objective),
    [i for i in r if value(x[i])>0.5]))