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