VISVESVARAYA TECHNOLOGICAL UNIVERSITY

Jnana Sangama, Belgavi-590018

A Mini Project Report on ADA(BCS401)

“KNAPSACK PROBLEM”
Submitted in partial fulfillment of the requirement for award of degree
of

BACHELOR OF ENGINEERING
in
COMPUTER SCIENCE AND ENGINEERING
DEENATHAYALAN(1EP22CS018)
MONISH K (1EP22CS060)
NAVEEN KUMAR (1EP22CS065)
MOHAMMEDFARHAN(1EP22CS57)
KUSHAL HIREMATH (1EP22CS050)
GAJENDRAN(1EP22CS024)
MOHAMMED CHAN ALAM(1EP22CS056)
MOHAMMED SHABAAZ(1EP22CS058)

Under the guidance of

Mrs. Divya U H
Asst. Professor
Dept. of CSE, EPCET

2023-2024
 CERTIFICATE

This is to certify that the Project work entitled “KNAPSACK PROBLEM” is a Bonafide work
carried by DEENATHAYALAN (1EP22CS018), MONISH (1EP22CS060), KUSHAL HIREMATH
(1EP22CS050), MOHAMMED FARHAN (1EP22CS057), MOHAMMES SHABAAZ(1EP22CS058),
GAJENDRAN (1EP22CS024), MOHAMMED CHAND ALAM (1EP22CS056), NAVEEN KUMAR
(1EP22CS065) in the partial fulfillment for the award of Bachelor of Engineering in

Computer Science and Engineering of Visvesvaraya Technological University, Belagavi,

during the year 2023- 2024. It is certified that corrections/suggestions indicated for Internal
Assessment have been incorporated in the report deposited in the departmental library. The
project report has been approved as it satisfies the academic requirements in respect of Project
work prescribed for the said Degree.

(Signature of the Guide) (Signature of the HOD)

Mrs. Divya U H Dr. I. Manimozhi
Asst. Prof HOD-CSE
Dept. of CSE, EPCET
Dept. of CSE, EPCET
 ACKNOWLEDGEMENT

First and foremost, we would like to express our sincere regards and thanks to
Management of East Point Group of Institutions, Bengaluru for providing us an opportunity
to work on the project “KNAPSACK PROBLEM”.

We are grateful to Dr. S Prakash, Senior Vice President, East Point Group of Institutions,
Bengaluru for his conscientious guidance and support that enabled us to complete this project.

We would like to express our gratitude to Dr. Mrityunjay V Latte, Principal, East Point
College of Engineering and Technology, Bengaluru for his constant support in completing the
project work successfully.

We would like to express our sincere thanks to Dr. I. Manimozhi, Professor and Head of the
Department of Computer Science and Engineering, EPCET for her valuable suggestions and
encouragement to do our best in this project work.

We would like to express our gratitude towards our guide Prof. Divya U H, Assistant Professor,
Department of CSE for her valuable guidance and constant supervision in completing the project
successfully.

Finally, we would like to thank all the faculty members of CSE department, our parents and friends
for their support and encouragement in successful completion of this project work.

DEENATHAYALAN (1EP22CS018)

MONISH K (1EP22CS060)

NAVEEN KUMAR (1EP22CS065)

MOHAMMED FARHAN (1EP22CS057)

GAJENDRAN V (1EP22CS024)

KUSHAL HIREMAT (1EP22CS050)

MOHAMMED CHAND ALAM(1EP22CS056)

MOHAMMED SHABAAZ(1EP22CS058)
iii
 ABSTRACT

The Knapsack Problem is a classic optimization problem with wide applications in fields such as
logistics, finance, and resource allocation. This project aims to develop a comprehensive system to
solve the Knapsack Problem using three distinct algorithms: Brute Force, Dynamic Programming, and
Memoization. Each algorithm provides a unique approach to determining the optimal set of items to
include in a knapsack to maximize the total value without exceeding its capacity.
The project includes a user-friendly interface for inputting item weights, values, and knapsack
capacity, allowing users to easily test and compare different algorithms. The Brute Force method,
while accurate, is computationally intensive with exponential time complexity, making it impractical
for large datasets. In contrast, the Dynamic Programming and Memoization approaches offer more
efficient solutions with polynomial time complexity, making them suitable for larger input sizes.
A detailed analysis is conducted to compare the time complexity, CPU time, and memory usage of
each algorithm. Experimental results are gathered through testing with various input sizes, providing
insights into the scalability and efficiency of each method. The system displays the optimal item
selection and their corresponding total values for each algorithm, highlighting the trade-offs between
accuracy and performanceFuture enhancements are proposed to address the limitations of current
algorithms, including improved memory efficiency, approximation methods, parallel computing, and
integration of real-world applications. These improvements aim to make the system more robust and
applicable to a broader range of optimization problems.
This project demonstrates the effectiveness of different algorithms in solving the Knapsack Problem
and provides a foundation for further research and development in optimization techniques

KEYPOINTS

 User Interface Design

 Performance Measurement

 Approximation Algorithms

 Memory Efficiency

 Parallel Computing

 Real-World Applications

iv
 CONTENTS
Chapter No. Description Page No

1 Introduction 1-3

1.1 About the Project

1.2 Problem Statement

1.3 Aim of the Project

1.4 Objectives of the Project

2 Requirement Specification 4-6

2.1 Hardware Requirements

2.2 Software Requirements

2.3 Functional Requirements

2.4 Non-functional Requirements

3 System Analysis & Design 7

3.1 Algorithm Used

4 System Implementation 8-10

4.1 Libraries/ Built-in Functions

4.2 Code

5 Result and Snapshots 11-12

6 Conclusion and Future Enhancement 13

6.1 Conclusion

6.2 Future Enhancement

References 14

v
KNAPSACK PROBLEM

Chapter 1

INTRODUCTION

The Knapsack Problem is a classic optimization problem that arises in various real-world
scenarios, such as resource allocation, budget management, and logistics. The essence of the
problem lies in selecting a subset of items, each with a given weight and value, to be placed in a
knapsack of limited capacity, with the goal of maximizing the total value without exceeding the
knapsack's capacity.This problem is well-known in the field of combinatorial optimization and has
been extensively studied due to its computational complexity. The Knapsack Problem can be
categorized as an NP-complete problem, meaning that the time required to find an exact solution
increases exponentially with the size of the input. As such, different approaches and algorithms
have been developed to solve it, each with varying degrees of efficiency and computational
resource requirements.In this project, we aim to explore and implement three distinct algorithms
to solve the Knapsack Problem: Brute Force, Dynamic Programming, and Memory Function
(Memoization). Each algorithm offers unique advantages and drawbacks in terms of
computational time, memory usage, and scalability. By comparing these algorithms, we can gain
insights into their practical applications and determine which method is most suitable for different
scenarios.The system developed will provide a user-friendly interface for inputting item data and
knapsack capacity, perform the necessary computations using the three algorithms, and then
analyze and compare their performance. This analysis will include a theoretical examination of
time complexity, as well as empirical measurements of CPU time and memory usage.
Additionally, experiments will be conducted with varying input sizes to observe the scalability
and efficiency of each algorithm.Through this study, we aim to deliver a comprehensive
understanding of the Knapsack Problem and the algorithms used to solve it, providing valuable
insights into their practical implementation and performance in different contexts.

Department of CSE, EPCET 2023-2024 Page 1

KNAPSACK PROBLEM

1.1 About the Project

This project focuses on solving the Knapsack Problem using three different algorithms:
Brute Force, Dynamic Programming, and Memory Function (Memoization). The Knapsack
Problem is a fundamental challenge in combinatorial optimization, where the objective is to
select a subset of items that maximizes the total value without exceeding a given capacity.
Each item has a specific weight and value, and the goal is to determine the optimal
combination of items that fit within the knapsack's weight limit.

1.2 Problem Statement

• Develop a system to solve the Knapsack Problem using three different algorithms:
Brute Force, Dynamic Programming, and Memory function. Also perform analysis.

• Provide a user-friendly interface for inputting item weights, values, and knapsack capacity.

• Analyze and compare the time complexity of each algorithm

• Measure and compare their performance in terms of computational resources (CPU time)
and memory usage.

• Conduct experiments with different sizes of input instances to observe scalability and
efficiency.

• Display the optimal selection of items and their total value for each algorithm.

1.3 Aim of the project

The aim of this project is to design, implement, and analyze a system capable of solving
the Knapsack Problem using three distinct algorithms: Brute Force, Dynamic Programming,
and Memory Function (Memoization). The project seeks to achieve the following specific
objectives:.

1.4 Objectives of the Project

 Implement Multiple Algorithms:
Develop and implement three distinct algorithms—Brute Force, Dynamic
Programming, and Memory Function (Memoization)—to solve the Knapsack

Department of CSE, EPCET 2023-2024 Page 2

KNAPSACK PROBLEM

 Analyze Time Complexity:

Theoretically evaluate and compare the time complexity of each algorithm,
identifying the computational demands associated with increasing problem size.
 Measure Computational Resources:
Conduct empirical measurements of CPU time and memory usage for each
algorithm, providing a practical assessment of their efficiency in handling the
Knapsack Problem.
 Conduct Scalability Testing:
Perform experiments with various input sizes to observe and analyze how each
algorithm scales, offering insights into their performance under different scenarios
and with larger datasets.
 Provide a User-Friendly Interface:
Design and develop an intuitive user interface that allows users to easily input item
weights, values, and knapsack capacity, and view the results of the algorithms in a
clear and accessible manner.
 Display Optimal Solutions:
Ensure that the system accurately identifies and displays the optimal selection of
items and their corresponding total value for each algorithm, allowing users to
compare the outcomes.
 Visualize and Compare Results:
Present the results of the algorithms through tables and graphical visualizations,
making it easier to compare their performance and understand the trade-offs
between different approaches.
 Enhance Algorithmic Understanding:
Provide users with a deeper understanding of the different strategies used to solve
the Knapsack Problem, including the strengths and weaknesses of each approach in
terms of computational efficiency and practicality.

Department of CSE, EPCET 2023-2024 Page 3

KNAPSACK PROBLEM

Chapter 2

REQUIREMENTS SPECIFICATION

2.1 Hardware Requirements

Processor:

• Intel Core i5 or equivalent.

• Clock Speed: 2.5 GHz or higher.

• Cores: Quad-core or higher.

Storage:

• 256 GB SSD minimum.

• Additional HDD storage for large datasets (optional): 1 TB

Input and Output devices:

• Monitor: Full HD resolution (1920x1080) or higher.

• Keyboard: Standard QWERTY keyboard.

• Mouse: Optical mouse with USB or wireless connectivity.

• Network: Ethernet port or Wi-Fi adapter for internet connectivity.

• Optional: External storage devices (USB drives, external hard drives) for data
backup and transfer.
2.2 Software Requirements

 Operating System: Windows 7 or later, macOS 10.12 or later Linux (any modern
distribution).

 Compiler: GCC (GNU Compiler Collection) for Linux and macOS, MinGW for
Windows.

 Command Line Tools: Terminal (macOS/ Linux) or Command Prompt/PowerShell

(Windows) for compiling and running the program.

Department of CSE, EPCET 2023-2024 Page 4

KNAPSACK PROBLEM

 Development Libraries: Standard C libraries: stdio.h, stdlib.h.

 Debugging Tools: GDB (GNU Debugger) for debugging C programs.

2.3 Functional Requirements

Input Handling
 Item Data Input:
o The system must allow users to input the number of items, and for each item,
specify its weight and value.
o Users should be able to input data manually through a form or upload a file (e.g.,
CSV) containing the item weights and values.
 Knapsack Capacity Input:
o The system must allow users to specify the knapsack's capacity (maximum weight
it can carry).
2. Algorithm Execution
 Brute Force Algorithm:
o The system must implement the Brute Force algorithm to generate all possible
combinations of items and select the combination that maximizes the total value
without exceeding the knapsack capacity.
 Dynamic Programming Algorithm:
o The system must implement the Dynamic Programming algorithm to solve the
Knapsack Problem using a table-based approach, ensuring the optimal solution is
found efficiently.
 Memory Function (Memoization) Algorithm:
o The system must implement the Memory Function approach to optimize the
recursive solution by storing previously computed subproblem results, reducing
redundant calculations.
3. Performance Measurement
 Time Complexity Analysis:
o The system must calculate and display the theoretical time complexity for each
algorithm.

Department of CSE, EPCET 2023-2024 Page 5

KNAPSACK PROBLEM

2.4 Non-Functional Requirements

1 . Performance
 Response Time:
o The system should provide results for small to medium-sized inputs (e.g., 10-50
items) within a reasonable time frame (e.g., a few seconds).
o For large input sizes (e.g., 100+ items), the system should efficiently manage
computational resources to ensure that the response time remains acceptable.
 Scalability:
o The system must be capable of handling increasingly larger datasets without
significant degradation in performance.
o The system should be designed to efficiently manage memory and CPU usage as
the size of the input data grows.
2. Usability
 Ease of Use:
o The user interface should be intuitive and user-friendly, allowing users with
minimal technical knowledge to input data and interpret results.
o Clear instructions and prompts should guide users through the process of entering
data and running the algorithms.
 Accessibility:
o The system should be accessible to users with different levels of expertise,
providing explanations or tooltips where necessary to help users understand the
algorithms and results.
 Error Messaging:
o The system should provide clear and informative error messages to help users
correct input errors or understand issues that may arise during processing.
3. Reliability
 Accuracy:
o The system must produce accurate results for each algorithm, ensuring that the
optimal solution is correctly identified based on the input data.
 Fault Tolerance:
o The system should be robust enough to handle unexpected inputs or conditions
(e.g., extremely large datasets) without crashing or producing incorrect results.

Department of CSE, EPCET 2023-2024 Page 6

KNAPSACK PROBLEM

Chapter 3

SYSTEM ANALYSIS &DESIGN

3.1 Algorithm

Greedy algorithm for the continuous knapsack problem

 Step 1 Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items given.
 Step 2 Sort the items in nonincreasing order of the ratios computed in Step 1. (Ties can be
broken arbitrarily.)
 Step 3 Repeat the following operation until the knapsack is filled to its full capacity or no
item is left in the sorted list: if the current item on the list fits into the knapsack in its
entirety, take it and proceed to the next item; otherwise, take its largest fraction to fill the
knapsack to its full capacity and stop.

Greedy algorithm for the discrete knapsack problem

 Step 1 Compute the value-to-weight ratios ri= vi/wi, i = 1, . . . , n, for the items given.
 Step 2 Sort the items in nonincreasing order of the ratios computed in Step1. (Ties can be
broken arbitrarily.)
 Step 3 Repeat the following operation until no item is left in the sorted list:➢ if the current
item on the list fits into the knapsack, place it in theknapsack and proceed to the next item;
otherwise, just proceed to thenext ite

Department of CSE, EPCET 2023-2024 Page 7

KNAPSACK PROBLEM

Chapter 4

SYSTEM IMPLEMENTATION
4.1 Libraries /Built-in Functions

• System Implementation: Libraries/Built-in Functions.

• Optimization Libraries: Use libraries like Google OR-Tools or SciPy for route
optimization algorithms.
• Data Processing: Employ Pandas for data manipulation and analysis.

• Geospatial Tools: Utilize Geo Pandas or GIS libraries for spatial data handling.

• Database Integration: Leverage SQL libraries for database interaction and

management.
• Real-Time Updates: Implement WebSocket or similar protocols for real-time
communication.

4.2 Code

MEMORY FUNCTION

const memoizationKnapsack = (items, capacity) => {

const n = items.length;
const memo = Array.from({ length: n }, () => Array(capacity + 1).fill(null));

const helper = (i, w) => {

if (i < 0) return { value: 0, items: [] };
if (memo[i][w] !== null) return memo[i][w];

const { value: excludeValue, items: excludeItems } = helper(i - 1, w);

let includeValue = 0;
let includeItems = [];

if (items[i].weight <= w) {
const { value: incValue, items: incItems } = helper(i - 1, w - items[i].weight);
includeValue = incValue + items[i].value;
includeItems = [...incItems, items[i]];
}

Department of CSE, EPCET 2023-2024 Page 8

KNAPSACK PROBLEM
if (includeValue > excludeValue) {
memo[i][w] = { value: includeValue, items: includeItems };
} else {
memo[i][w] = { value: excludeValue, items: excludeItems };
}

return memo[i][w];
};

return helper(n - 1, capacity);

};

DYNAMIC
const dynamicProgrammingKnapsack = (items, capacity) => {
const n = items.length;
const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

for (let i = 1; i <= n; i++) {

for (let w = 0; w <= capacity; w++) {
if (items[i - 1].weight <= w) {
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - items[i - 1].weight] + items[i - 1].value);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}

let w = capacity;
const selectedItems = [];
for (let i = n; i > 0 && w > 0; i--) {
if (dp[i][w] !== dp[i - 1][w]) {
selectedItems.push(items[i - 1]);
w -= items[i - 1].weight;
}
}

return { maxValue: dp[n][capacity], items: selectedItems };

};

Department of CSE, EPCET 2023-2024 Page 9

KNAPSACK PROBLEM

BRUTE FORCE
const bruteForceKnapsack = (items, capacity) => {
const n = items.length;
let maxValue = 0;
let bestCombination = [];

const helper = (i, currentWeight, currentValue, currentItems) => {

if (i === n) {
if (currentValue > maxValue) {
maxValue = currentValue;
bestCombination = [...currentItems];
}
return;
}

if (currentWeight + items[i].weight <= capacity) {

helper(i + 1, currentWeight + items[i].weight, currentValue + items[i].value,
[...currentItems, items[i]]);
}

helper(i + 1, currentWeight, currentValue, currentItems);

};

helper(0, 0, 0, []);
return { maxValue, items: bestCombination };
};

Department of CSE, EPCET 2023-2024 Page 10

KNAPSACK PROBLEM

Chapter 5

RESULTS AND SNAPSHOTS

Result:

Department of CSE, EPCET 2023-2024 Page 11

KNAPSACK PROBLEM

Department of CSE, EPCET 2023-2024 Page 12

KNAPSACK PROBLEM

Department of CSE, EPCET 2023-2024 Page 13

KNAPSACK PROBLEM

Department of CSE, EPCET 2023-2024 Page 14

KNAPSACK PROBLEM

Chapter 6

CONCLUSION AND FUTURE ENHANCEMENT

6.1 Conclusion

 All three methods provide the correct and optimal solution to the Knapsack Problem,
but the time taken to reach this solution varies significantly based on the algorithm
used and the size of the problem
 Brute Force: While the brute force method guarantees the correct solution by
evaluating all possible combinations, its time complexity of O(2n)O(2^n)O(2n) makes
it impractical for large input sizes. It quickly becomes computationally expensive as
the number of items increases.
 Dynamic method provides an efficient solution with a time complexity of O(n×W)O(n
\times W)O(n×W), making it suitable for moderate to large inputs. It strikes a good
balance between accuracy and performance, but its space complexity can become a
concern as the knapsack capacity increases.
 The experiments conducted demonstrate that the Dynamic Programming and
Memoization methods scale much better with increasing input sizes compared to the
Brute Force method. These approaches are more suitable for real-world applications
where the number of items and knapsack capacity are large.
 The memoizaion approach also offers an efficient solution similar to dynamic
programming, with the added benefit of potentially reduced computation time by
avoiding redundant calculations. However, it also shares the same space complexity
challenge as dynamic programming.

Department of CSE, EPCET 2023-2024 Page 15

KNAPSACK PROBLEM

6.2 Future Enhancement

 Space Optimization in DP/Memoization: Future work could explore space optimization

techniques such as using a 1D array instead of a 2D array in the dynamic programming
solution to reduce memory usage from O(n×W)O(n \times W)O(n×W) to
O(W)O(W)O(W).

 Sparse Memoization: Another enhancement could involve using sparse data structures or
compressed storage for the memoization table, especially when many entries are unused.
For extremely large instances where even dynamic programming becomes infeasible,
exploring approximation algorithms like the Greedy method or Fully Polynomial Time
Approximation Scheme

REFERENCES

 Referred from you tube.

 Referred from ChatGPT.
 Website: Wikipedia: Knapsack Algorithm.
 www.davbyjan.comknapsack Algorithm Visualizer - by Jan S.

Department of CSE, EPCET 2023-2024 Page 16

KNAPSACK PROBLEM

Department of CSE, EPCET 2023-2024 Page 17

KNAPSACK PROBLEM

Department of CSE, EPCET 2023-2024 Page 18