for many problems, no known polytime algorithm
for each subset
if weight ok and value best-so-far
print subset, update best-so-far-value
def powerset(iterable): # all subsets
#https://docs.python.org/2/library/itertools.html#recipes
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def bruteforce(n,val,wt,W):
indices = range(n) # [0 1 .. n-1]
bestVal = 0
for indexset in powerset(indices):
v, w = 0, 0
for t in indexset:
v+= val[t]
w+= wt[t]
if w <= W and v > bestVal:
bestVal = v
print indexset, w, v
runtime ?
Ω(2n)
correct ?
yes: considers every subset
can we do better ? ? ?
subproblems ?
by set of allowed items
by allowed total weight
set of allowed items ?
{1} {1 2} {1 2 3} ...
allowed total weight ?
0 1 2 ...
K[w][j]: best value with items 1..j, total wt ≤ w
compute K[w][j]
item j out? value K[w][j-1]
item j in? value K[w-w_j][j-1] + v_j
so set K[w][j] to max of these two
#python indexing: val[t],wt[t] corresponds to K[][t+1]
# K[w][j] will be best value knapsack, weight at most w,
# using subset of { item_1, item_2, ..., item_j }
# warning: K[][] needs an extra 0th column, so its indices
# are off-by-one w.r.t. val[], wt[]
# eg. val[v], wt[t] refer to t+1'st item
# also K[][t+1] refers to t+1'st item
def solveknapsack(val,wt,W):
n = len(val)
K = [[0 for j in xrange(n+1)] for w in xrange(W+1)]
for j in range(1,n+1):
for w in range(W+1):
K[w][j] = K[w][j-1] if w < wt[j-1] \
else max(K[w][j-1], K[w-wt[j-1]][j-1]+val[j-1])
max value knapsack, weight at most 27 ? val [ 6, 9, 7, 9, 8, 7] wt [11, 6, 8, 10, 8, 9] 0 [ 0, 0, 0, 0, 0, 0, 0] 1 [ 0, 0, 0, 0, 0, 0, 0] 2 [ 0, 0, 0, 0, 0, 0, 0] 3 [ 0, 0, 0, 0, 0, 0, 0] 4 [ 0, 0, 0, 0, 0, 0, 0] 5 [ 0, 0, 0, 0, 0, 0, 0] 6 [ 0, 0, 9, 9, 9, 9, 9] 7 [ 0, 0, 9, 9, 9, 9, 9] 8 [ 0, 0, 9, 9, 9, 9, 9] 9 [ 0, 0, 9, 9, 9, 9, 9] 10 [ 0, 0, 9, 9, 9, 9, 9] 11 [ 0, 6, 9, 9, 9, 9, 9] 12 [ 0, 6, 9, 9, 9, 9, 9] 13 [ 0, 6, 9, 9, 9, 9, 9] 14 [ 0 ? ? ? ? ? ?] 14 [ 0, 6, 9, 16, 16, 17, 17] 15 [ 0, 6, 9, 16, 16, 17, 17] 16 [ 0, 6, 9, 16, 18, 18, 18] 17 [ 0, 6, 15, 16, 18, 18, 18] 18 [ 0, 6, 15, 16, 18, 18, 18] 19 [ 0, 6, 15, 16, 18, 18, 18] 20 [ 0, 6, 15, 16, 18, 18, 18] 21 [ 0, 6, 15, 16, 18, 18, 18] 22 [ 0, 6, 15, 16, 18, 24, 24] 23 [ 0, 6, 15, 16, 18, 24, 24] 24 [ 0, ? ? ? ? ? ?] 24 [ 0, 6, 15, 16, 25, 26, 26] 25 [ 0, 6, 15, 22, 25, 26, 26] 26 [ 0, 6, 15, 22, 25, 26, 26] 27 [ 0, 6, 15, 22, 25, 26, 26] ----------------------------- solution 24 [0, 1, 0, 1, 1, 0] val 26
consider these instances
each value and weight has n bits, so in [ 2n-1 ... 2n -1 ]
average weight ( 2n-1+2n -1 ) / 2 ≈ .75 2n
let W be n times average weight, so ≈ .75 n 2n
input size Θ( n2 ) bits
brute force wc time
2n subsets, each weight Θ(n) bits
for each subset t of size s, perform s add'ns
total number of add'ns is sum, over all subsets t, of size(t)-1
sum, over all subsets t, of size(t) is n*2n-1 (pair each subset with its complement)
total number add'ns: n*2n-1 - 2n in Θ( n * 2n)
avg add'n involves n/2 weights, sum has Θ( n2 ) bits, time Θ(n2)
total alg'm time in Θ( n3 2n )
dyn. prog. wc time
avg wt. Θ(n2) bits
avg add'n cost Θ(n2)
wc W Θ(n * 2n)
Θ(n2 * n * W ) = Θ( n4 2n ), worse than BF!
let t = n2 so n = √ t let f(t) = t2 2√t
each alg. input Θ( t ) bits wc time O( f(t) )
2O(log t) polynomial
2o(t) subexponential
2Ω(t) exponential
here
limt → ∞ 2k log t / f(t) = 0, so f(t) superpoly
f(t)/2t = t2 2√t / 2t = t2 (2 / 2√t)√t
limt → ∞ f(t) / 2t = 0, so f(t) subexp
how do you like DPW if
each weight is in { 2^{n-1}, ..., 2^n -1 } and
each values is in { 1, ..., 2n } ?
organize subproblems by value (instead of weight)
also useful in constructing knapsack PTAS (polytime approx scheme)
def knapDPV(val,wt,V): #dynamic programming by value
# A[v][j] is min weight of subset of items 0..j with exact val v
infinity = 1 + sum(val) #larger than any possible sum of values
n = len(val)
A = [[infinity for j in xrange(n)] for v in xrange(V+1)]
for j in range(n): A[0][j] = 0
A[val[0]][0] = wt[0] # end initialization
for v in range(1,V+1): # row 0 already initialized
for j in range(1,n): # column 0 " "
A[v][j] = A[v][j-1] if v < val[j] \
else min(A[v][j-1], A[v - val[j]][j-1] + wt[j])
time in O(nV), but V can be big
correctness ?
from random import randint
from itertools import chain, combinations
def powerset(iterable):
#https://docs.python.org/2/library/itertools.html#recipes
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def settostring(s,n): # set as pretty binary string
x = ''
for j in range(n):
if j in s: x += ' *'
else: x += ' -'
return x
def gensubset(a,b,n): # subset of 0..n-1, each with prob a/b
s = set()
for j in range(n):
if randint(1,b) <= a: s.add(j)
return s
def initsubsets(n,m,a,b): # m subs of 0..n-1
# an element in a subset with probability a/b
L = [] # list of subsets
for _ in range(m): L.append(gensubset(a,b,n))
sumlen = 0
for x in L:
sumlen += len(x)
print settostring(x,n)
print 'universe size', n,' avg subset size', sumlen*1.0/m
return L
def bruteforce(n,m,L):
indices = range(m) # [0 1 .. m-1]
bestcover = ()
for indexset in powerset(indices):
subsetunion = set()
for t in indexset:
subsetunion |= L[t]
# indexsets sorted by cardinality, so first found is min
if len(subsetunion) == n:
print 'size', len(indexset), 'cover', indexset
for j in indexset: print settostring(L[j],n)
return # so return once one is found
n,m,a,b = 40,25,2,11
L = initsubsets(n,m,a,b)
bruteforce(n,m,L)
set universe
0 1 2 3 4 5 6 7 8 9
0 - - * - - - - * * -
1 - * - - - - - * - *
2 - - - - * - - * * -
3 - - - - - - - - * -
4 - - - - - * - * * -
5 - - - - * - * * - *
6 * * - * - - - - - -
7 - - - - - - * * - -
min cover (0, 4, 5, 6)
0 - - * - - - - * * -
4 - - - - - * - * * -
5 - - - - * - * * - *
6 * * - * - - - - - -
set universe
0 1 2 3 4 5 6 7 8 910111213141516171819
0 * - * - - - * - * - - - - * - * - - * -
1 - - - * - * - * - - - * - - * * - - - -
2 - * - - - - * - * - - - - - - - - * - -
3 - - - * - - - - - - - - - - - - - - * -
4 * - - - - * - * - * - - - - - * - - - -
5 - - - * - - * * - - - - - * - * - - - -
6 - - - - - * - - * - - * * - - * - - * -
7 - * - - * - - - * - * * * - * * - - - -
8 - * - - * - - - * - - - - * * - - - * *
9 * - * - - - * * - - - - - - - - - - - *
10 - * - - - - * - - * * - * - - - * - * -
min cover (0, 1, 2, 8, 10)
0 * - * - - - * - * - - - - * - * - - * -
1 - - - * - * - * - - - * - - * * - - - -
2 - * - - - - * - * - - - - - - - - * - -
8 - * - - * - - - * - - - - * * - - - * *
10 - * - - - - * - - * * - * - - - * - * -
Dasgupta et al. section 5.4
- input: some towns, and a threshold distance (e.g. 30 km)
- problem: build schools in minimum number of towns,
s.t. distance to school at most the threshold
- model as a graph problem G = (V,E)
- V = set of towns
- E = pairs of towns at most threshold distance apart
- for each town, its neighbor-set is set of all towns
whose distance away is at most the threshold
- problem: pick the minimum number of neighbor-sets that cover V
- in other words: this is an instance of min set cover
- answer: NP-hard, by reduction from vertex cover
given a boolean formula in CNF, is it satisfiable?
assume input has n variables and m clauses
brute force: 2n possible assignments
brute force: worst case time O(m2n)
( x1 or ~x2 or x3 ) and ( x1 or ~x2 or x4 ) and ( x1 or x2 or x3 ) and ( x1 or x2 or x4 ) and (~x1 or ~x2 or ~x3 ) and (~x1 or ~x2 or x3 ) and (~x1 or x2 or x4 ) and ( x2 or ~x3 or ~x4 ) and ( x2 or x3 or ~x4 ) [ 1, -2, 3] [ 1, -2, -4] [ 1, 2, 3] [ 1, 2, 4] [ -1, -2, -3] [ -1, -2, 3] [ -1, 2, 4] [ 2, -3, -4] [ 2, 3, -4] satisfiable (0, 1, 1, 0)
[ -4, -5, 6] [ -4, 5, -6] [ -2, 4, -5] [ -2, 5, -6] [ -1, -3, -4] [ -1, -3, 4] [ -1, 4, -6] [ 1, -4, 5] [ 1, -3, -5] [ 1, -3, 4] [ 1, 5, -6] [ 2, 5, 6] [ 3, -5, -6] [ 4, -5, 6] [ 4, 5, -6] [ 4, 5, 6] satisfiable (1, 1, 0, 1, 0, 0)
# I/O: literals x1 -x1 x2 -x2 ... rept'd by 1 -1 2 -2 ...
def clause_sat(clause,asnmt):
for var in clause:
if ((var>0 and asnmt[ var-1 ] == 1) or
(var<0 and asnmt[-(var+1)] == 0)):
return True
return False
def sat(formula, asnmt):
for clause in formula:
if not clause_sat(clause,asnmt): return False
return True
n, k, m = 20, 3, 90 #max m: (n choose k)(2^k)
myf = formula(n,k,m)
show(myf, False)
allAsn = product([0,1],repeat=n)
for a in allAsn:
if sat(myf,a): print 'satisfiable', a