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