1. Project Overview

This repository contains a theoretical and practical analysis of algorithms for the 0/1 Knapsack Problem. The 0/1 Knapsack Problem is a combinatorial optimization problem where, given a set of items, each with a weight and a value, the objective is to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Each item can only be selected once.

The goal of this project, as detailed in the accompanying report (Raport.pdf), is to implement, compare, and analyze three distinct algorithmic paradigms for solving this problem:

1. An exhaustive search method (Backtracking).
2. A pseudo-polynomial exact method (Dynamic Programming).
3. A fast heuristic method (Greedy).

The analysis focuses on identifying the practical performance limits and accuracy trade-offs of each approach by executing them against a systematically generated suite of difficult test instances.

2. Algorithmic Theory & Logic

The theoretical foundation for this project is presented in Raport.pdf. It includes a formal proof of the Knapsack Problem's NP-Hardness and a detailed analysis of each implemented algorithm.

Complexity Class

The Knapsack optimization problem is NP-Hard. As demonstrated in the report, this is proven via a polynomial-time reduction from the Subset Sum Problem (SSP), which is known to be NP-Complete. This theoretical underpinning establishes the problem's computational difficulty and justifies the exploration of non-exact, heuristic methods for large-scale instances.

Algorithms

Three distinct algorithmic paradigms were chosen to highlight the fundamental trade-offs between execution time, memory consumption, and solution optimality.

1. Backtracking Method

   • Logic: An exhaustive search algorithm that uses a recursive Depth-First Search (DFS) to explore the entire solution space. For each item, it makes a binary choice: either include it in the knapsack or not.
   • Complexity Analysis:
     • Time: $O(2^n)$. The algorithm explores a binary decision tree of depth n, leading to exponential runtime. It is computationally infeasible for anything beyond small academic instances (e.g., n > 30).
     • Space: $O(n)$, required to maintain the recursion stack.

2. Dynamic Programming (DP) Method

   • Logic: An exact algorithm that solves the problem by breaking it down into simpler subproblems. It uses memoization to avoid redundant calculations, storing the maximum value achievable for every discrete capacity up to the maximum capacity W. The implementation is based on the Bellman equation: dp[w] = max(dp[w], dp[w - wi] + pi).
   • Complexity Analysis:
     • Time: $O(n \cdot W)$. The complexity is dependent on the number of items n and the knapsack capacity W. This is classified as a pseudo-polynomial time complexity because the runtime is polynomial in the value of W, but exponential in the number of bits required to represent W.
     • Space: $O(W)$. The implementation uses a space-optimized 1D array to store the DP state.

3. Greedy Method (Heuristic)

   • Logic: A non-optimal, heuristic approach that aims to find a good solution quickly. It operates in three steps: 1) Calculate the value-to-weight ratio for each item. 2) Sort items in descending order based on this ratio. 3) Iterate through the sorted list, adding items to the knapsack if they fit.
   • Complexity Analysis:
     • Time: $O(n \log n)$, dominated by the initial sorting operation.
     • Space: $O(n)$, for storing the items to be sorted.

3. Implementation Details

• Language: The algorithms and benchmarking framework are implemented in Java.
• Core Logic:
  • The src/knapsack/ package contains the Java classes for each algorithm: Backrack_Method.java, DP_Method.java, and Greedy_Method.java.
  • The Produs.java class serves as the data structure for knapsack items.
• Benchmarking Engine:
  • tests.Benchmark.java is the main executable class. It orchestrates the process of reading test data, invoking the solvers, and recording performance metrics.
  • Crucially, it contains safeguards to prevent the execution of Backrack_Method and DP_Method on problem instances that would be computationally intractable, demonstrating a practical awareness of their theoretical limits.

4. Experimental Results

A comprehensive experimental evaluation was conducted, with full results and graphical analysis available in Raport.pdf. The tests were run on a suite of procedurally generated datasets based on Pisinger's taxonomy, ensuring a thorough examination of algorithmic performance on non-trivial instances (e.g., Uncorrelated, Weakly/Strongly Correlated).

Key Findings:

• Backtracking: The algorithm hits a "hard exponential wall" and becomes impractical at approximately N=26 items, with runtime doubling at each step.
• Dynamic Programming: This method provides optimal solutions robustly but is limited by memory (OutOfMemoryError) when the knapsack capacity W becomes very large, as its space complexity is $O(W)$.
• Greedy Heuristic: This method is exceptionally fast, providing near-instantaneous results even for thousands of items. However, its accuracy is highly sensitive to the input data structure.
  • On Uncorrelated data, the error was negligible (<2%).
  • On Almost Strongly Correlated data, it produced the highest average error (6.15%).
  • On specific small, Strongly Correlated instances, the error peaked at 39%, demonstrating a clear trade-off between speed and optimality.

The report concludes that the optimal choice of algorithm is contextual. A hybrid strategy is recommended: use an exact method (DP or Backtracking) for small n, DP for large n with small W, and the Greedy heuristic for scenarios where speed is critical and a margin of error is acceptable.

5. Setup & Usage

Prerequisites

• Java Development Kit (JDK 11+)
• GNU Make

Instructions

All commands should be run from within the src/ directory.

1. Compile Project:

   make build

   This compiles all source files into the ../bin directory.

2. Run Benchmark:

   make run

   This executes the tests.Benchmark class. It reads input from ../tests/teste_progresive.csv and writes results to ../tests/rezultate_progresive.csv.

3. (Optional) Regenerate Test Data:

   make generate

   This runs the tests.Generator class to create a new set of test instances.