StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Using a simple greedy algorithm will not provide any bounds on the quality of the solution in comparison to OPT.</p> <p>Here is a fully polynomial time (1 - epsilon) * OPT approximation psuedocode for knapsack:</p> <pre><code>items = [...] # items profit = {...} # this needs to be the profit for each item sizes = {...} # this needs to be the sizes of each item epsilon = 0.1 # you can adjust this to be arbitrarily small P = max(items) # maximum profit of the list of items K = (epsilon * P) / float(len(items)) for item in items: profit[item] = math.floor(profit[item] / K) return _most_prof_set(items, sizes, profit, P) </code></pre> <p>We need to define the most profitable set algorithm now. We can do this with some dynamic programming. But first lets go over some definitions.</p> <p>If P is the most profitable item in the set, and n is the amount of items we have, then nP is clearly a trivial upper bound on the profit allowed. For each i in {1,...,n} and p in {1,...,nP} we let Sip denote a subset of items whose total profit is <em>exactly</em> p and whose total size is minimized. We then let A(i,p) denote the size of set Sip (infinity if it doesn't exist). We can easily show that A(1,p) is known for all values of p in {1,...,nP}. We will define a recurrance to compute A(i,p) which we will use as a dynamic programming problem, to return the approximate solution.</p> <pre><code>A(i + 1, p) = min {A(i,p), size(item at i + 1 position) + A(i, p - profit(item at i + 1 position))} if profit(item at i + 1) < p otherwise A(i,p) </code></pre> <p>Finally we give _most_prof_set</p> <pre><code>def _most_prof_set(items, sizes, profit, P): A = {...} for i in range(len(items) - 1): item = items[i+1] oitem = items[i] for p in [P * k for k in range(1,i+1)]: if profit[item] < p: A[(item,p)] = min([A[(oitem,p)], \ sizes[item] + A[(item, p - profit[item])]]) else: A[(item,p)] = A[(oitem,p)] if (oitem,p) in A else sys.maxint return max(A) </code></pre> <p><a href="http://rads.stackoverflow.com/amzn/click/3540653678" rel="nofollow">Source</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload