In this paper, we present a novel optimization algorithm for assigning weapons to targets based on desired kill probabilities. For the given weapons, targets, and desired kill probabilities, our optimization algorithm assigns weapons to targets that satisfy the desired kill probabilities and minimize the overkill. The minimization of overkill assures that any proper subset of the weapons assigned to a target results in a kill probability that is less than the desired kill probability on such a target. Computational results for up to 120 weapons and 120 targets indicate that the performance of this algorithm yields an average improvement in quality of solutions of 26.8% over the greedy algorithms, whereas execution times remained on the order of milliseconds.