### Knapsack Problem - new algorithm

Posted:

**Wed Jun 29, 2011 10:04 am**Hello, i want to introduce you my algorithm for solving Knapsack Problem

http://en.wikipedia.org/wiki/Knapsack_problem

Can you tell me if i'm wrong, but i thing it is BETTER than DP algorithms

Knapsack problem algorithm.

Nikolay Nedelchev Bulgaria, Sofia e-mail : nickndn@gmail.com

Let’s have a set of objects O={oi}, i = 1,2…n each object having a weight and value.

Let’s have a set of objects S = {si}, I = 1,2..m, each object being an unique subset of O.

Each object of S has value which is the total value of all the objects oi in the represented subset of O, and weight, formed in the same way.

S contains:

1. Every subset of O except those which have a smaller value than at least one of the other subsets with the same or smaller weights. (and except those which have same value with at least one of the other subsets with the smaller weights)

see Clarification

2. Only one of the subsets with exact same weights and values, no matter which.

Let S be sorted by descending weights.

The so formed set S, has the following properties:

Property A: The so defined set S contains all the possible best answers for all the possible knapsacks for which there is a valid solution.

Property B: Each object in S is the best answer for at least one possible knapsack.

Property C: The list is sorted by weight.

Property D: The list is sorted by value (because of 1.).

Let’s have a new object p of type O.

Let’s have a new set T = {ti} of type S, which contains all the objects from S, but each subset is augmented with the object p, so the value of each object of T, ti , is equal to the value of si plus the value of p. The same applies to the weight.

T has all the same properties A(*), B(*), C, D.

Let’s add p to T, as a singular subset in the right position, in order to preserve the sort order by weight.

The so formed set T has lost properties B and D, but has kept properties A(*) and C.

* It follows from Prop A, that the set T contains the solutions to all the possible knapsacks if t should be present in the solution.

As a reminder, S contains all the solutions if t should not be present.

So, we can create a new set S, which is formed from merging the old S and T, keeping with 1. and 2.

The new set S has all the properties A.B.C and D for the new set O including object p.

The time complexity of the construction of the new set S takes O(N) time, with N being equal to the size of the old set S.

If at the time of the execution of the so presented algorithm, all the O objects and the capacity of the knapsack are known, all the sets S can be optimized according to the currently found best solution and input information, i.e. we can add to points 1. and 2. a new point 3. That the weight of the subsets in S does not exceed the capacity of the knapsack and etc.

Because all the operations described here on S take a linear time, it follows that the overall time complexity of the algorithm is O(S1+S2+S3…SN) (the sum of the sizes of all the sets S i.e. from definition of S : m1 + m2… mn) .

Clarification to 1.

If we have o1(w = 2, v = 9) and o2(w = 4, v = 8 ) .

Then S = { s1 = (o1) , s2 = ( o1 + o2) }

We do not need the o2 object as a singular subset and will never need the o2 object in a subset that does not contain the o1 object

NOTES:

1. With a suitable representation in memory, every object in S can take constant space and the solution can be extracted in O(n) time, n = size of solution. Also in general there is no need to keep all objects of all sets S.

2. If we compare this algorithm to the currently available dynamic programming algorithms we will note that the sum of all the sizes sets S which we have created, is smaller or equal to the size of the table, which we would have allocated (and calculated) during DP, in other words, the time and space complexities of the algorithm are always smaller or equal to the complexity of the DP algorithms

3. The algorithm can be used with all kinds of input data, including real, negative (as well as very big), etc, numbers as weights.

4. We don’t need to calculate the last set of subsets S

5. The algorithm can be easily transformed to the algorithm of Horowitz and Sahni.

Please tell me about errors and other uncertainties.

If you are interested, i can send you source code, builded test cases, DOC file with algorithm description adn ect.

http://en.wikipedia.org/wiki/Knapsack_problem

Can you tell me if i'm wrong, but i thing it is BETTER than DP algorithms

Knapsack problem algorithm.

Nikolay Nedelchev Bulgaria, Sofia e-mail : nickndn@gmail.com

Let’s have a set of objects O={oi}, i = 1,2…n each object having a weight and value.

Let’s have a set of objects S = {si}, I = 1,2..m, each object being an unique subset of O.

Each object of S has value which is the total value of all the objects oi in the represented subset of O, and weight, formed in the same way.

S contains:

1. Every subset of O except those which have a smaller value than at least one of the other subsets with the same or smaller weights. (and except those which have same value with at least one of the other subsets with the smaller weights)

see Clarification

2. Only one of the subsets with exact same weights and values, no matter which.

Let S be sorted by descending weights.

The so formed set S, has the following properties:

Property A: The so defined set S contains all the possible best answers for all the possible knapsacks for which there is a valid solution.

Property B: Each object in S is the best answer for at least one possible knapsack.

Property C: The list is sorted by weight.

Property D: The list is sorted by value (because of 1.).

Let’s have a new object p of type O.

Let’s have a new set T = {ti} of type S, which contains all the objects from S, but each subset is augmented with the object p, so the value of each object of T, ti , is equal to the value of si plus the value of p. The same applies to the weight.

T has all the same properties A(*), B(*), C, D.

Let’s add p to T, as a singular subset in the right position, in order to preserve the sort order by weight.

The so formed set T has lost properties B and D, but has kept properties A(*) and C.

* It follows from Prop A, that the set T contains the solutions to all the possible knapsacks if t should be present in the solution.

As a reminder, S contains all the solutions if t should not be present.

So, we can create a new set S, which is formed from merging the old S and T, keeping with 1. and 2.

The new set S has all the properties A.B.C and D for the new set O including object p.

The time complexity of the construction of the new set S takes O(N) time, with N being equal to the size of the old set S.

If at the time of the execution of the so presented algorithm, all the O objects and the capacity of the knapsack are known, all the sets S can be optimized according to the currently found best solution and input information, i.e. we can add to points 1. and 2. a new point 3. That the weight of the subsets in S does not exceed the capacity of the knapsack and etc.

Because all the operations described here on S take a linear time, it follows that the overall time complexity of the algorithm is O(S1+S2+S3…SN) (the sum of the sizes of all the sets S i.e. from definition of S : m1 + m2… mn) .

Clarification to 1.

If we have o1(w = 2, v = 9) and o2(w = 4, v = 8 ) .

Then S = { s1 = (o1) , s2 = ( o1 + o2) }

We do not need the o2 object as a singular subset and will never need the o2 object in a subset that does not contain the o1 object

NOTES:

1. With a suitable representation in memory, every object in S can take constant space and the solution can be extracted in O(n) time, n = size of solution. Also in general there is no need to keep all objects of all sets S.

2. If we compare this algorithm to the currently available dynamic programming algorithms we will note that the sum of all the sizes sets S which we have created, is smaller or equal to the size of the table, which we would have allocated (and calculated) during DP, in other words, the time and space complexities of the algorithm are always smaller or equal to the complexity of the DP algorithms

3. The algorithm can be used with all kinds of input data, including real, negative (as well as very big), etc, numbers as weights.

4. We don’t need to calculate the last set of subsets S

5. The algorithm can be easily transformed to the algorithm of Horowitz and Sahni.

Please tell me about errors and other uncertainties.

If you are interested, i can send you source code, builded test cases, DOC file with algorithm description adn ect.