Algorithm implementations for solving the classic Knapsack problem, applied to financial investment optimization. The challenge is to select the best combination of stocks to purchase in order to maximize profit while adhering to a fixed budget.

Goals

The goal is to maximize return on investment while adhering to a budget of 500 euros. The challenge is to determine the best combination of stocks to buy to achieve the highest possible profit within the shortest possible time.

Algorithmic Approaches

To address this problem, we explored two distinct algorithmic approaches:

Brute Force Algorithm

• Description: This algorithm explores all possible combinations of purchases to identify the one that maximizes profit. Although this method guarantees an optimal solution, it is generally impractical for large datasets due to its high computational cost.
• Disadvantages:
  • High computation time
  • Impractical for large datasets

Dynamic Programming Algorithm

• Description: Dynamic programming breaks down the main problem into simpler sub-problems and uses the solutions of these sub-problems to build a global optimal solution. This method is more efficient for handling complex, large-scale problems.
• Advantages:
  • Significant reduction in computation time by avoiding unnecessary recalculations
  • Notable improvement in speed and efficiency compared to brute force

Impact

• Resource Optimization: Using dynamic programming allows for more effective allocation of financial resources, increasing profits while adhering to budget constraints.
• Efficiency: The optimized algorithms demonstrate significant performance improvements, allowing for rapid resolution of complex problems compared to traditional methods.

Scripts and codes are available here

See on Github