0
$\begingroup$

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'.

  • 0
    Knapsack problem ideas may help http://en.wikipedia.org/wiki/Knapsack_problem2012-08-08

1 Answers 1

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.