python - Algorithm Approaches to NP Multiple Constraint Knapsack P -

i've been delving python , programming in general first time on past few weeks. posted question multiple constraint knapsack problem little while ago , figured out how write brute force solution.

i found several other similar questions (knapsack constraint python , 01 knapsack specialization) none addressed problem. figured post preposed solution , open criticism , review.

but there little issue. issue around 100 trillion possible combinations, think np complete (am using term correctly?). wondering if had recommendations how make algorithm more efficient or comments on code in general. , tolerance of ignorance appreciated.

thanks again

ehc

from itertools import combinations import csv import codecs  #opens , formats data csv doc  out=open("/users/edwardcarter/documents/pp/bb_test_data.csv","rt") data=csv.reader(out) data=[[row[0],row[1],eval(row[2]),eval(row[3])] row in data] out.close()  #sort players position  c=[] pf=[] pg=[] sf=[] sg=[]  in data:     n in i:         if n == 'c':             templist =             c.append(i[1])                    elif n == 'pf':             templist =             pf.append(i[1])         elif n == 'pg':             templist =             pg.append(i[1])         elif n == 'sf':             templist =             sf.append(i[1])         elif n == 'sg':             templist =             sg.append(i[1])  #creat dictionaries of players value , price  names=[] invalue=[] inprice=[] in data:     templist =     names.append(i[1])     invalue.append(i[2])     inprice.append(i[3])  prices = dict(zip(names,inprice)) values = dict(zip(names,invalue))  #data input , scrubbing complete  choices=[] s=60000     # salary cap n=50   # number of choices display num_c = 1 #number of players allowed each position num_sg = 2 num_pf = 2 num_sf = 2 num_pg = 2 #creat combinations c_to_take in combinations(c,num_c):     sg_to_take in combinations(sg,num_sg):         pf_to_take in combinations(pf,num_pf):             sf_to_take in combinations(sf,num_sf):                 pg_to_take in combinations(pg,num_pg):                     things_to_take = c_to_take+sg_to_take+pf_to_take+sf_to_take+pg_to_take                     price = sum(prices[a] in things_to_take)                     value = sum(values[a] in things_to_take)                     if price<=s , price>=(s-5000):                         choices.append([value,price,things_to_take]) value,price,things_to_take in sorted(choices,reverse=true)[:n]:     print(value,price,things_to_take) 

i'll take crack, though not sure entirely understand question. 1 thing suggest general coding perspective use pandas package handle data. has nice import csv function , handle lot of dancing have data.

for answer question, depends on motive. if want know how solve problem or if want answer question. 5 nested for-loops , many possible solutions don't think best road. if want write own solution try looking approximation , branch , bound methods solving problem. there plethora of papers deal knapsack problem (might suggest one?) , can take crack @ applying methods. getting answer perspective openopt. has knapsack problem optimizer may able handle problem. code like:

from openopt import * items = ['''define dictionary of items'''] constraints = lambda values: (''' define constraints in format:                                   values['item1] < num, etc.''') objective = 'string name of item optimized' knapsack = ksp(objective, items, goal = 'max', constraints = constraints) solution = knapsack.solve('solver-name', iprint = 0) 

in case items of variables: position, money etc. constraints number of players per position , salary cap (ex: values['money'] > 60000). helps.