import numpy as np
import time
# http://en.wikipedia.org/wiki/Knapsack_problem
def fill_knapsack(weights, values, maxweight, seed):
n = weights.size
# random solution
rnd = np.random.RandomState(seed)
perm = rnd.permutation(n)
# find how many we can fit in the knapsack
weights = weights[perm]
sum_weights = np.cumsum(weights)
# first index that is False
p = np.argmin(sum_weights < maxweight)
# which items are included
included = perm[:p]
# compute total value of what we included
score = values[included].sum()
return score, included
# number of items
n = 1000
# allowed knapsack weight
maxweight = n / 4.0
# number of random samples
ntry = 10000
# make reproducible
np.random.seed(0)
weights = np.random.rand(n)
values = np.random.rand(n)
# perform experiments
t0 = time.time()
tries = [fill_knapsack(weights, values, maxweight, seed) for seed in range(ntry)]
t1 = time.time()
best_score, best_combination = max(tries)
print "n=%d maxweight=%g ntry=%d best_score=%g (%d items, weight %g) time %.3f s" % (
n, maxweight, ntry, best_score, best_combination.size, weights[best_combination].sum(), t1 - t0)
if False:
# plot at which rank the scores arrive
scores = [score for score, _ in tries]
best_score = np.maximum.accumulate(scores)
from matplotlib import pyplot
pyplot.plot(best_score)
pyplot.show()