#!/usr/bin/python
from collections import deque
import sys

#script requires two args:
#1/0 for using Pi sub in the weight
#ub -- the upper bound for the sensors (int)

def inslist(s, delta, d):
    if len(s) == 0: 
        s.append(d)
        return
    #move backwards Through list
    for i in xrange(len(s)-1, -1, -1):
        if delta[i] >= delta[d]: s.pop()
        else:
            s.append(d)
            break
'''
W = 10
n = 3
v = [11,15,10]
w = [5,3,1]
c = [2,4,6]
'''
if len(sys.argv) == 1: 
    print "Please supply args"
    sys.exit(0)
sub = True if sys.argv[1] == "1" else False
BUDGET = 100000
HOMES = 200
FNAME = "mss.csv"
f = open(FNAME, 'w')
f.write("W,c,sensor,quantity\n")
f.close()
n = 6 
#ub = 3
ub = int(sys.argv[2])
SUB = 50 + 75 + 100 + 33 #cloogy + smartplugs + gas + gsm/2
#v = [11,31,21,31,33] #CO2, humidity, light, sound, temp
v = [18,6,12,19,27,9]
rw = [200,5,10,5,100,2]
w = [i + 75/n for i in rw]
#names = ["CO2", "Humidity", "Light", "Sound", "Temperature"]
names = ["C", "P", "H", "L", "S", "T"]
eff = [v[i]/float(w[i]) for i in xrange(n)]
items = [i[0] for i in sorted(enumerate(eff), key=lambda x:x[1])]
v = [v[i] for i in items]
w = [w[i] for i in items]
eff = [eff[i] for i in items]
#print w
cvec = [1,2,3,5,10,20,50]
wvec = [50,100,200,500,1000,5000]
fi = open(FNAME, 'a')
for W in wvec:
    for ub in cvec:
        c = [ub]*n
        c = [c[i] for i in items]
        #W = BUDGET/HOMES
        if sub: W -= SUB
        #print "With a budget of %d per home, and %d homes:" % (W, HOMES)
        f = [[0 for i in xrange(n+1)] for j in xrange(W+1)]
        delta = [0 for i in xrange(W+1)]
        s = deque()

        itemsets = [[[0 for i in xrange(n+1)] for i in xrange(n+1)] for j in xrange(W+1)]

        for i in xrange(1, n+1):
            for d in xrange(W+1): delta[d] = d*eff[i-1] - f[d][i-1]
            for r in xrange(0, w[i-1]):
                d0 = r
                d = r + w[i-1]
                k = 1
                s = deque()
                while d <= W:
                    if f[d][i-1] < f[d0][i-1] + k*v[i-1]:
                        f[d][i] = f[d0][i-1] + k*v[i-1]
                        itemsets[d][i] = list(itemsets[d0][i-1])
                        itemsets[d][i][i] = itemsets[d0][i-1][i] + k
                        inslist(s,delta,d)
                        d += w[i-1]
                        if k < c[i-1]: k+=1
                        else: 
                            d0 = s.popleft()
                            k = (d - d0)/w[i-1]
                    else:
                        f[d][i] = f[d][i-1]
                        itemsets[d][i] = itemsets[d][i-1]
                        d0 = d
                        k = 1
                        d += w[i-1]
                        s = deque()

        mss = itemsets[W][n][1:]
        #print "Optimum value is %d" % f[W][n]
        #print "At a cost of %d" % sum([w[i] * mss[i] for i in xrange(n)])
        #print "Optimum quantities are: "
        #re-sort
        so = [i[0] for i in sorted(enumerate(items), key=lambda x:x[1])]
        mss_sorted = [mss[i] for i in so]
        #for i in xrange(n): print "%d of %s" % (mss_sorted[i], names[i])
        for i in xrange(n): fi.write("%d,%d,%s,%d\n" % (W, ub, names[i], mss_sorted[i]))

fi.close()
