Knapsack Problem - new algorithm

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
nickndn
New poster
Posts: 2
Joined: Wed Jun 29, 2011 10:00 am

Knapsack Problem - new algorithm

Post by nickndn » 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.

nickndn
New poster
Posts: 2
Joined: Wed Jun 29, 2011 10:00 am

Re: Knapsack Problem - new algorithm

Post by nickndn » Fri Jul 01, 2011 3:47 pm

I. Integer item weight.

Let's review how the DP algorithm works and focus on the important points.

Let N be the item count, and M - the capacity of the knapsack. The DP algorithm constructs a table with dimensions M * N, and calculates for EVERY possible knapsack with capacity <= M all N possible solutions, for items (1), (1,2), (1,2,3)..(1,2..N), i.e Omega(M*N).

One of the bigger problems with this algorithm is that in practise it has to solve "similar problems", which give one and the same solution. Because knapsacks with capacities M-4 and M-5 can have identical solutions, but the DP algorithm has to calculate them both, no matter what.

Let's have a completely different look at the knapsack problem.

Let's ask ourselves how many knapsacks which are smaller or equal in capacity than M and have ONLY DIFFERENT BEST SOLUTIONS, exist(solutions with different total value and weight, all solutions with equal total weight and value are considered as a single solution, and only one of them is used, no matter which). Let these different solutions form the set S.

It's obvious that the size of S is <= M (eg: if M = 1000, there is no way that 1001 problems with different solutions exist, when there are 1000 possible knapsack capacities {M=1000})

Let's also note that the solution from S with largest value (and it's also the one with largest weight, because if a solution with greater weight and smaller value existed, it wouldn't be present in the set, because it wouldn’t be BEST solution for any knapsack) will be our solution for knapsack with capacity M.

This means that if we can build the set S with time and space complexity O(S*N) in sorted form, we can get to the solution of the initial problem by another O(1) operations and because S <= M, this algorithm would be better or at least equal (in the special cases) to the DP algorithm.

Post Reply

Return to “Algorithms”