An Exact Dynamic Programming Algorithm and GRASP Heuristic for the Backpack Problem with Progressive Battery Discounts

This work studies a variation of the Backpack Problem, called the Knapsack Problem with Progressive Discounts. In this issue, the items are organized in stacks, and the cost associated with each item is progressively reduced as a greater number
of its predecessors in the same stack is selected, in accordance with business practices that
offer quantity discounts, such as on wholesale purchases or service packages. Além
In addition, precedence restrictions are considered between the items, representing scenarios in which
The selection of certain elements depends on the previous choice of others. For the resolution of
Problem Two approaches are proposed: an exact algorithm based on dynamic programming
with pseudo-polynomial complexity and a GRASP heuristic. Computational experiments
showed that the heuristics presented an average gap of less than 5% in relation to
Optimal solutions obtained for the evaluated instances.