Lab Experiment-6 PDF
Document Details
Marwadi University
Tags
Summary
This document details a lab experiment on the 0/1 Knapsack problem. It covers the theory, algorithm, and Python code for implementing the solution. The experiment is from Marwadi University.
Full Transcript
**1. 0/1 Knapsack Problem** **Theory:** The 0/1 Knapsack problem is a classic optimization problem where you are given a set of items, each with a weight and a profit (or value). The goal is to determine the maximum profit you can obtain by selecting items to include in a knapsack, such that the t...
**1. 0/1 Knapsack Problem** **Theory:** The 0/1 Knapsack problem is a classic optimization problem where you are given a set of items, each with a weight and a profit (or value). The goal is to determine the maximum profit you can obtain by selecting items to include in a knapsack, such that the total weight does not exceed a given capacity. **Algorithm**: **Programming Language:** **Code:** def knapsack(capacity, weights, profits): n = len(weights) ratio = \[(profits\[i\] / weights\[i\], weights\[i\], profits\[i\]) for i in range(n)\] ratio.sort(reverse=True, key=lambda x: x\[0\]) profit\_value = 0 for r, weight, profit in ratio: if weight \
