Dynamic Knapsack Problem

Source: [Bra02]

The knapsack problem is a well known in combinatorial optimization. The static problem's objective is filling a knapsack with objects, so that their accumulated value is maximized.

The most popular model of change for the dynamic problem consists in modifying the maximum capacity of the knapsack. This is expressed mathematically as follows:

where n corresponds to the number of objects, xi to a binary variable which represents whether the i-th object is selected or not, and vi and wi respectively the value and weight of the i-th object.

Note: This site is updated regularly.


Powered By