I have a set of $N$ items to fill a knapsack with maximum capacity $W$ and the maximum number of items that the knapsack can carry is $N_{m}$ items. The problem can be formulated as following:

max $\sum_{i=1}^{N} w_{i}x_{i}$

subject to

C1: $\sum_{i=1}^{N}w_{i}x_{i}\le W$.

C2: $\sum_{i=1}^{N}x_{i}\le N_{m}$.

C3: $x_{i}\in {0,1}$

Note that the profits are the same as the weights. The size of the problem maybe large, for example, $N=500$ and the weights are floating point (non integers).

As far as I know, dynamic programming can not be used as the weights are not integers. Therefore, I am thinking of using branch and bound (B&B). As this problem has a special structure where the profits and the weights are equal, I wonder if this simplifies the problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.