The knapsack problem

The greedy is corruption, so you can't exceed your capacity. This is called the knapsack problem. You add the value in your napsack, not items.

S⊆I

S is a subject, and I is items.

You maximize the value of your items.

B is the capacity, so your items are restricted.

i∈I

You use dynamic programing for optimization.

A(j) is the array. j=1,・・・,n.

(t,w) is in A(j). t≦B and w is the value.

(t',w') is t≦t' and w≧w'. (t,w) can't expand the space in your napsack, but the value is increased.

If (t, w) dominates (t', w') and (t', w') dominates (t'', w''), then (t, w) also dominates (t'', w'').

A(j) is (tk, wk), so (B+1, V+1) is possible because of integers.

A(1)={(0,0), (s1,w1)}

A(j)←A(j-1), (j=2,．．．,n )

(t, w)∈A(j-1), (t+sj, w+wj)∈A(j), t+sj≦B

You remove A(j), so A(j-1) and (sj, wj) are remained.

Then you return (t, w) and A(n).

max(t,w)∈A(n)^w

This is not polynomial time because of the binary.

Θ(nB)

This would be polynomial because of vagueness. Both t and all B may be valuable.

(1-ε) is approximation algorithm for maximization.