1
$\begingroup$

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.

$\endgroup$

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.