Performance Comparison of Greedy and Dynamic Programming Algorithms for E-Commerce Shopping Cart Discount Optimization Using the Online Retail UCI Dataset

Abstract

E-commerce platforms heavily rely on automated promotional strategies, such as tiered discounts, to enhance customer loyalty. Therefore, this study aims to analyze the performance of computational algorithms in determining item priorities within a shopping cart under promotional budget constraints. The 0/1 Knapsack Problem was addressed by comparing two computational approaches: Dynamic Programming (DP) and the Greedy Algorithm. Transaction data from the UCI Online Retail dataset were cleaned and aggregated into 3,746 unique product catalogs, then simulated using a promotional budget limit of £499.40 with a 10% discount policy. Computational experiments revealed contrasting trade-off characteristics between the two approaches. The DP algorithm guaranteed an absolute optimal solution with a total profit of £2,725,575.77 but required 28.10 seconds of computation time. In contrast, the Greedy algorithm completed the selection process in a fraction of a second (0.17 seconds) while incurring only a marginal profit deficit of 0.01%. The Greedy heuristic approach proved to be highly practical and efficient for integration into real-time user interface systems, whereas the superior accuracy of DP makes it more suitable for offline database processing and inventory analytics research.