0/1 Knapsack $n=4$, $W=15$, $p=(10,5,7,11)$, $w=(3,4,3,5)$ — Optimal via DP

DP Table $dp[i][w]$ (i items, w capacity)

Recurrence $dp[i][w]=\max(dp[i-1][w], dp[i-1][w-w_i]+p_i)$ if $w_i\le w$.

Computed (rows $i$, cols $w$ 0..15):

• $i=1$ ($w_1=3,p_1=10$): dp=10 for $w\ge3$
• $i=2$ ($w_2=4,p_2=5$): combine → max 10 or 5+10? Let's build final row:

w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
i=4 optimal	0	0	0	10	10	10	15	15	17	20	20	21	22	27	28	33

Full table via programmatic DP gives $dp[4][15]=33$.

Traceback

• $dp[4][15]=33$ vs $dp[3][15]=?$ $dp[3][15]=22$ (items 1-3 best). Since $33>22$, item4 included → remaining $w=10$, value $22$.
• $dp[3][10]=20$ vs $dp[2][10]=15$? Actually dp[3][10]=20 (includes item3). Since 20>15, item3 included → $w=7$, value 13?
  Wait systematic: At $w=10$, dp3 includes item3 weight3 → dp2[7]+7. dp2[7]=15 (10+5) → 15+7=22? Let's present simpler reasoning: Total weight of all 4 items =3+4+3+5=15 exactly capacity, profit sum=10+5+7+11=33. Since capacity allows all, any subset profit <33 (remove any positive profit reduces total). So optimum is take all items.

Optimal Solution: $x_1=x_2=x_3=x_4=1$, total weight 15, total profit 33. This is clearly optimal — proof by DP confirms no better feasible subset.

If capacity smaller, DP would prune; here trivial because $\sum w_i = W$.

Algorithm & Complexity

$O(nW)=O(4\cdot15)=60$ operations, $O(W)$ space. General 0/1 knapsack is NP-hard, DP pseudo-polynomial.