Word Count : 796

---

We are given a 0/1 Knapsack problem with: * Number of items, n = 7 * Capacity of knapsack, M = 15 * Profits (P): (12, 4, 14, 8, 9, 20, 3) * Weights (W): (3, 2, 5, 6, 4, 1, 7) --- We will solve it using Dynamic Programming. Let’s define a DP table `K[i][w]` that represents the maximum profit using first `i` items and a knapsack capacity of `w`. So, we construct a table `K` of size `(n+1) x (M+1)`. ### Step 1: Initialize the table Let `K[0][w] = 0` for all `w` (0 capacity yields 0 profit), and `K[i][0] = 0` for all `i` (no items yields 0 profit). ### Step 2: Fill the table using the recurrence: For each item `i = 1 to n`, and each weight `w = 0 to M`: If `W[i-1] <= w`: * `K[i][w] = max(K[i-1][w], K[i-1][w - W[i-1]] + P[i-1])` Else: * `K[i][w] = K[i-1][w]` --- We build this step by step: Let’s write the arrays again for reference: | i | P\[i-1] | W\[i-1] | | - | ------- | ------- | | 1 | 12 | 3 | | 2 | 4 | 2 | | 3 ___ ______ ________ ________ _______ _______ ______ __________.
___ ______ ____ _____ ________ _____ ___ _________ _________ ____.
________ ________ _____ ______ ____.
____ ____ __________ ________ ________.
_______ _____ _______ ___ ________ _________ _____ _________.
_________ ___ __________ ________ _________ _________ _____ _________.
_________ ___ ________ _________ _________ __________ ___ _____.
__________ ______ ___ _______ _____ ____ ___ __________ ________ ________ ____.
__________ __________ ____ _________ __________ __________ _________ _______.
_______ __________ _________ __________ __________ ___ ____.
_________ _____ ______ ________ _______ _____ __________.
________ _________ _______ _______ __________ ____ ________ ______ _________ _______.
__________ ___ ____ ______ ____ _______ ______ ___.
___ _________ _______ _______ _________ _________.
__________ ___ _____ _______ ____ _________ _______.
____ _____ _______ __________ __________ ____ _______ ______.
____ ________ __________ _______ ____ ________ _________ ___.
_______ ____ _________ ___ ___ __________.
__________ ______ ________ ______ __________ ____.
_____ _____ ____ _________ _______ _____ ______ ____.
________ ___ _______ ____ ______ _____.
__________ ____ _______ _______ __________ ____ __________.
_____ __________ ___ __________ _________ ___.
________ _____ __________ ___ _______.
_________ _______ ____ ____ _____ ____.
_________ _________ ___ _____ _____ ________.
___ ______ ____ _________ ________.
________ ____ ______ __________ ______.
_______ ________ ________ _________ ___ _________ _________ _________ ____.
__________ ______ _________ ________ _______.
___ ______ ___ __________ ________ _______ ___ ____.
_____ ______ ________ ___ ________ __________.
______ __________ _________ _______ ________ _____ ___ ________.
________ ________ _____ ____ _________.
___ _________ ______ ________ _____.
________ ______ _________ _________ ___ ____ _______ _________ _________ ____.
__________ ______ _________ _______ __________ _________ _______ _________ _________ __________ __________.
________ ___ _______ _____ _____ _____ __________ __________ _______.
__________ _____ ___ ________ _____ ___ ______ ______.
__________ ______ _____ ______ _______ _________ _______ _____ ___.
_________ _________ _____ __________ __________.
____ ___ _________ ______ ______ _____ ______ ____ ____ __________ ______ _____.
___ ______ ___ ____ ___ _________.
______ _____ _________ ____ ___ _____ ______ ________ _______ __________ ___ ______.
________ ________ ___ ___ ________ ____ ___ ___ _________ ______ _______ _________.
__________ _______ ______ __________ _______ __________ ___ _________ ______.
______ ____ ______ ____ __________ ________ _______ ______ _______.
___ __________ _________ ___ ___ ___ _________ ______ __________ ________ ___.
__________ ________ _________ ___ __________ ___.
________ ____ ____ _____ __________ __________ __________ _______.
________ ________ _______ __________ ____ ___ _______.
__________ __________ ______ __________ ____ _________ __________.
____ _________ _________ ___ ___ _________ _____ _____ __________ ____ ______ _________.
_________ _____ ________ ___ __________ _____ _______ _________.
__________ ________ _________ ___ ______.
_________ ______ ___ _________ ________.
______ _____ ________ __________ ____ _________ ________ _________ _____.
______ ___ _________ ___ _______ __________.
_________ __________ ____ _____ _______.
___ ______ _________ ______ _________ _______ _______ ______ ________ _________ _______.
____ _________ ________ _______ ____ ___.
__________ ________ ______ ______ _________ _________ _________ ______.
__________ ________ _____ ________ ____ _______ _________ ______ _____ ________.
__________ _____ __________ ____ _____ _________.
_______ _____ __________ _________ _________ _____ _______ ______.
_________ __________ ________ _______ ___ _______.
_______ __________ _________ ____ ___ ___ ________.
_____ _____ __________ ________ _____ _________ _____ ____ __________ __________.
____ _________ ___ ____ _____ _________.
___ ___ ______ ____ ________ _______ ___ ____ _____.
___ _____ ________ _____ _________ ____ ______ _________ __________ _________.
______ _____ __________ _________ ___ ________ ___ _______ ____ ____ _______.
_________ __________ _____ _____ ______ __________ ________ ________.
______ _____ _________ ________ ________ ______ _________.
_____ _____ ________ _______ _______ ____ ______ ___.
___ _____ ____ __________ _______ _______ _____.
______ ______ ______ ________ _______ __________ __________ _________ _________.
_________ _______ _____ ______ _______.
Get Full Answer on WhatsApp