Thursday, October 23, 2008

Complementary Knapsack problem

Every programmer (or almost every programmer) heard of the faimos problem called, The knapsack problem. This problem can be formulated in math way: Having a set of numbers, find a subset of numbers this set and their sum are under or equal than a given value?
The solution of this is very simple and there are many web-sites where you can find the implementaion or the pseudo-code.

We name "Complementary Knapsack problem" the problem where we must find a subset that sum is greater than a given value and the difference of the sum and the given number is minimum.
I've done some research using Google and I found nothing(maybe I haven't searched enough).

The solution of this problem is solving the Knapsack problem for the a value equal with: sum of all numbers in set minus the given value. Because this problem offers an optimal solution, if we remove from out set of numbers the result of this problem, we find our subset and if we sum them we get a number grater that the given value and the difference is minimum.

No comments: