Question

Find the optimal solution for the knapsack instance n=7 and M=15

(P1, P2__________________________________Pn) = (12, 4, 14, 8, 9, 20, 3)

(W1, W2,________________________________ Wn) = (3, 2, 5, 6, 4, 1, 7)

28 May 2025
Answer :
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 | 14 | 5 | | 4 | 8 | 6 | | 5 | 9
________ ______ __________ ___ _________ _________ _______ _______ _____ ______ __________ ____.
______ _______ _____ ________ _______.
________ ___ _________ ___ ____ ______.
_________ _______ ________ ____ _____ __________ ______.
___ ________ __________ _______ __________ ______ _____ _______.
_____ _________ _______ ______ __________ ____.
________ _______ _______ _______ ___ _______ ____.
_____ _______ __________ _______ _________ _________ ________.
_______ __________ __________ _______ _________ ___ _______ ____ _______ _____.
___ ________ _______ __________ ___ _________ ___ ______.
________ ____ _____ ______ ________ _________ ______ ____ _________.
_____ _______ _________ ____ _________ _________ ___ ___ __________ ________ _______.
____ _____ ________ ______ ___ ___ ______ ____ ________ ______ _______ _________.
__________ _____ _______ _____ _________ __________ ________ ___ _______.
____ _________ ______ __________ _______ ________ ________.
________ _________ __________ ____ ___ ______ ______ ___ _____ _______ ____.
_______ _____ __________ _____ _______ ________.
_______ _______ __________ _____ ________ ___ ____.
___ _________ _______ ____ ___ ____ ____ ________ ____.
_______ ______ _____ ___ ___ ________ _______ ___ __________.
_______ __________ _______ ___ ___ _______.
____ __________ ____ _________ _________ __________ ________ ________ ___ _____ _____.
____ ___ ________ _________ _______ _________ _____ _________ ________ ___.
______ _____ _________ _______ ___ ____ __________ _______ _____ _____ ______.
_______ __________ ______ ____ ___.
_________ ______ __________ _________ _________ ________ ___ _____.
_________ _____ _________ ____ ________ ________ _________ _____.
_____ _________ ______ ___ ________ _______ _______.
_______ _____ ___ __________ _______ ___ _______ _______ ____ __________ ____ _________.
____ ___ ______ __________ __________ ___ _____ _______ ____ ________ ___.
_______ _________ _______ _______ ________.
____ _______ ____ ___ ___ ________.
________ __________ __________ __________ ____ ________ ___ _________ ________ __________ _________ ______.
_________ ___ _________ _______ _________ ________ ____ ____ _________.
________ _____ ______ __________ ___ ______ ____ ___ ___ __________ ____ ____.
______ _______ __________ ___ _____ _____ __________ _______ __________ ______ _____.
_______ ___ ________ _________ ________ _____ _________ ______.
______ ______ ____ ____ __________ ____ __________ _______ ______ ____.
_____ _____ _________ _____ _________ ___ _________.
_______ ________ _________ ____ _________ __________.
______ ______ ________ ______ _____ _______ _______ ________ ______ ________ _____.
_______ ______ __________ _______ _______ ______ __________ _____ ________.
___ ______ ______ ___ ______ _________.
______ _______ __________ ________ _______ ________ ______ ____ _________ ___.
_______ _____ ________ _________ _______ ____ ___ ___ ___ _______.
___ _______ __________ ______ ____ ________ ______ __________ _______ ____.
____ _____ ____ ________ ___ __________ ____ ____ _____.
_____ _________ _________ __________ ________ _________ _______.
__________ ______ __________ ____ ________ ________ __________.
_____ _______ _________ ________ ______ ____.
________ _________ ____ ____ __________ _________ _______.
_____ ____ __________ ______ ____.
________ _________ ___ ___ ________ _______ _________ ______.
________ ___ ___ _________ _____ ________ __________ __________ ___ _______ _____ ___.
___ _____ ____ _________ __________.
_____ ________ ________ ______ ________ ______ ________.
____ ___ ____ _____ ____ _______.
__________ _______ __________ _____ _____ ______ ______ _______ ________ __________ _______ _________.
______ ______ _____ _______ __________ _______ ____ ____ _________.
__________ __________ ______ ___ ______ ____.
_____ ____ _________ _________ ________ ___ _______ ________ _____ __________ _____ __________.
________ _______ ________ _______ ___ _________ _____ _________ ______ ________.
_______ ______ ________ ___ _______ ____.
_________ _____ ________ ___ ___.
_____ __________ ____ ______ __________ ____ ____.
_____ _______ ____ ___ ______ ____ ______ ___ __________ _______.
______ __________ _____ _________ _______ __________ _______ _________ __________.
____ _______ _____ _________ __________ ___ _______ ___.
_________ _____ _______ __________ _____ ______ ____ ___ ________ _________.
_______.
IGNOU ACADEMY
Your IGNOU journey, made easier.
  • Solved Assignments
  • Study Notes
  • Guess Papers
  • Question Papers
Skip in 10
Top
📞
Call Support Instant phone assistance IGNOU BCS 42 2024 2025 - Find the optimal solution for the knapsack instance n=7 and M=15(P | IGNOU Academy
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→