How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Question

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such that total weight of the items always sums up to value 'W' (non-negative integer) and total number of items cannot exceed 'n'.

Answer 1

Let $x_i = 1$ if the $i^{th}$ item is selected and $0$ otherwise. The optimization problem now becomes:

$\mathbf{x}^* = \arg \min_{\mathbf{x}} \mathbf{x}^T\mathbf{c}$

subject to:

$\mathbf{x}^T\mathbf{w} = W$

$\mathbf{x}^T\mathbf{1} \leq n$

$x_i \in \{0,1\}\quad\forall i$

This is a integer (binary) linear programming problem, and is NP-hard. Many algorithms such as the cutting-plane method iteratively solve this problem by replacing it with a simpler non-integral linear programming problem and making adjustments to the constraints such that the solution comes closer to an integer.