0/1 knapsack problem | Dynamic Programming Application

0/1 knapsack problem

1.  An object is either included or not included in the knapsack. i.e., x_i = 0/1, 1 ≤ i≤ n Thus the problem can be stated as:
                                                                    And x_i = 0 or 1, I <= i <= n
2. Fractional knapsack problem exhibits greedy choice property. Greedy algorithm exists.
3. 0/1 knapsack problem does not exhibits greedy choice property. No greedy algorithm exists.
4. It exhibits optimal substructure property. Only dynamic programming algorithm exists.
5. Let Sⁱ represent the possible states resulting from the decision sequences
   Sⁱ = { (P,W) }
   Where P – total profit earned
              W – total weight of objects included
   Sⁱ ₁ = { (P,W) / (P-p_i, W-w_i) E Sⁱ }
   Sⁱ⁺¹ = Sⁱ + Sⁱ₁