Knapsack Python C846Cd

Question: **0/1 Knapsack Problem Python Example** **Problem Statement** 1. Given a knapsack with capacity 7 and 5 items, each having weight and profit. 2. Maximize total profit without exceeding capacity. 3. Each item can be taken once or not at all. **Python Code Example** 1. Define weights and profits arrays. 2. Initialize DP table with zeros. 3. Fill DP table using bottom-up approach. 4. Determine maximum profit. 5. Find which items are included. **Code Explanation** 1. For each item and capacity, decide to include or exclude item. 2. If item fits, compare profits including or excluding it. 3. Store maximum profit in DP table. 4. Backtrack to find included items. ```python weights = [3, 2, 4, 5, 1] profits = [50, 40, 70, 60, 30] capacity = 7 n = len(weights) # Initialize DP table K = [[0 for x in range(capacity + 1)] for x in range(n + 1)] # Build table K[][] in bottom up manner for i in range(1, n + 1): for w in range(1, capacity + 1): if weights[i-1] <= w: K[i][w] = max(profits[i-1] + K[i-1][w - weights[i-1]], K[i-1][w]) else: K[i][w] = K[i-1][w] max_profit = K[n][capacity] # Find included items w = capacity included_items = [] for i in range(n, 0, -1): if K[i][w] != K[i-1][w]: included_items.append(i) w -= weights[i-1] included_items.reverse() print('Maximum Profit:', max_profit) print('Items included:', included_items) ``` **Output:** - Maximum Profit: 120 - Items included: [1, 3] If you want to access the full transcript press the button bellow ERROR: Invalid YouTube URL. Please provide a valid YouTube video URL.