﻿==================================================
6. 0/1 KNAPSACK (DYNAMIC PROGRAMMING)
==================================================

ALGORITHM:
1. Read the weight and profit of each item.
2. Create DP table of size (n+1) x (W+1).
3. Initialize the first row and column with zero.
4. Check whether the current item fits.
5. If it fits, calculate inclusion and exclusion values.
6. Store the maximum of both values.
7. Otherwise, copy the previous row value.
8. Find maximum profit from dp[n][W].
9. Backtrack to find selected items.

RECURRENCE RELATION:

If w[i] <= w:

V(i,w) = max { V(i-1,w),
               V(i-1,w-w[i]) + P[i] }

If w[i] > w:

V(i,w) = V(i-1,w)

BASE CONDITIONS:
V(0,w) = 0
V(i,0) = 0

TIME COMPLEXITY:
Best Case    : O(nW)
Average Case : O(nW)
Worst Case   : O(nW)
Space        : O(nW)

IMPORTANT:
1. 0/1 Knapsack does not allow fractions of items.