Click here to Skip to main content
15,867,330 members
Home / Discussions / Algorithms
   

Algorithms

 
AnswerRe: C# Hash Sum - Add Bytes Pin
BobJanova5-Jul-11 1:14
BobJanova5-Jul-11 1:14 
GeneralRe: C# Hash Sum - Add Bytes Pin
David19875-Jul-11 2:01
David19875-Jul-11 2:01 
Questionfind all 'n'-bit numbers with 'k' bit set [modified] Pin
Sameerkumar Namdeo1-Jul-11 23:46
Sameerkumar Namdeo1-Jul-11 23:46 
AnswerRe: find all 'n'-bit numbers with 'k' bit set Pin
David19872-Jul-11 0:15
David19872-Jul-11 0:15 
GeneralRe: find all 'n'-bit numbers with 'k' bit set Pin
Sameerkumar Namdeo2-Jul-11 1:01
Sameerkumar Namdeo2-Jul-11 1:01 
QuestionSewer Colony Optimization Algorithm Pin
Anubhava Dimri30-Jun-11 18:05
Anubhava Dimri30-Jun-11 18:05 
AnswerRe: Sewer Colony Optimization Algorithm Pin
Roger Wright30-Jun-11 19:05
professionalRoger Wright30-Jun-11 19:05 
QuestionKnapsack Problem Algorithm [modified] Pin
Nikolay Nedelchev29-Jun-11 8:24
Nikolay Nedelchev29-Jun-11 8:24 
Hello,
I want ask you to read my algorithm for solving Knapsack Problem and tell me if i'm wrong or if there is similar algorithm


If you are interested, i can send you source code, description and etc.

Knapsack problem algorithm.
Nikolay Nedelchev Bulgaria, Sofia e-mail :
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.

The Algorithm:
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.

modified on Friday, July 1, 2011 12:07 PM

AnswerRe: Knapsack Problem Algorithm Pin
OriginalGriff30-Jun-11 9:26
mveOriginalGriff30-Jun-11 9:26 
QuestionLine Intersection Pin
musefan17-Jun-11 3:20
musefan17-Jun-11 3:20 
AnswerRe: Line Intersection Pin
dasblinkenlight17-Jun-11 5:51
dasblinkenlight17-Jun-11 5:51 
GeneralRe: Line Intersection Pin
musefan17-Jun-11 5:55
musefan17-Jun-11 5:55 
AnswerRe: Line Intersection Pin
Roger Wright17-Jun-11 20:34
professionalRoger Wright17-Jun-11 20:34 
GeneralRe: Line Intersection Pin
musefan21-Jun-11 0:12
musefan21-Jun-11 0:12 
AnswerRe: Line Intersection Pin
BobJanova20-Jun-11 23:41
BobJanova20-Jun-11 23:41 
GeneralRe: Line Intersection Pin
musefan21-Jun-11 0:08
musefan21-Jun-11 0:08 
QuestionPattern Cracking Question Pin
YSLGuru16-Jun-11 12:57
YSLGuru16-Jun-11 12:57 
AnswerRe: Pattern Cracking Question Pin
Moreno Airoldi17-Jun-11 22:52
Moreno Airoldi17-Jun-11 22:52 
AnswerRe: Pattern Cracking Question Pin
dasblinkenlight20-Jun-11 9:36
dasblinkenlight20-Jun-11 9:36 
AnswerRe: Pattern Cracking Question Pin
musefan21-Jun-11 0:34
musefan21-Jun-11 0:34 
GeneralRe: Pattern Cracking Question Pin
YSLGuru21-Jun-11 10:41
YSLGuru21-Jun-11 10:41 
GeneralRe: Pattern Cracking Question Pin
BobJanova22-Jun-11 0:33
BobJanova22-Jun-11 0:33 
GeneralRe: Pattern Cracking Question Pin
musefan22-Jun-11 3:34
musefan22-Jun-11 3:34 
GeneralRe: Pattern Cracking Question Pin
BobJanova22-Jun-11 4:34
BobJanova22-Jun-11 4:34 
Questionmerge k AVL trees complexity Pin
Hesham Yassin16-Jun-11 0:14
Hesham Yassin16-Jun-11 0:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.