A question about Knapsack problem (discrete math)

kappa_am · 2013-12-20 07:02:44

Hi all,
I have a problem in engineering which can be done by dynamic programming known as knapsack problem in computer and math science.
the problem is:
I have a set of numbers (n numbers) and I like to find a subset that add up to specific number. the complexity of this problem is O(2^n). so it is time consuming process. In first step I like to determine is there any subset if the answer be yes then dynamic programming runs to find subset.

so there is my question: is there any way to find whether there is a subset that add up to specific number by formula without examining all possibilities (dynamic programming) ? I don't need to find the subset! just I want a yes or no.

thank you:)

bobbym · 2013-12-20 07:04:47

Hi;

That is a partitioning problem. What do the numbers look like?

kappa_am · 2013-12-20 07:47:53

the problem is somewhat complicated in express! the set is variable according to condition. I have a main set which in it the smallest number is 1 and the greatest number is N(N-1) (N is number of set's members). but the set which I like find a subset that add up to the specific number is itself a subset of the main set. mid numbers in main set have difference more than 2, and there is no repeated number. the knapsack is of 01 kind (we cannot choose a number twice or more). the desired number is smaller than largest number in main set but can be larger than the greatest number in set which I like to find the subset that add up to this number.
Example:
desired number:8
the main set:1, 3, 7, 12
the set can be 1, ,3, 7 or any other subset of above set.

Thank you very much for taking your valuable time on this problem.

bobbym · 2013-12-20 11:08:20

Yes, there are ways to tell whether or not a set or subset of numbers will add up to some number.

kappa_am · 2013-12-20 19:25:19

would you please explain how?

Thank you

bobbym · 2013-12-20 22:38:01

Hi;

Should have phrased it as might be a way. Maybe using generating functions. Can you provide a good example, so I can get an idea of the complexity of the generating functions?

kappa_am · 2013-12-20 23:34:51

lets simplify and look to the problem of another perspective:
there is a main set of number in which the smallest number is 1. the midst numbers can be variable but i am sure that every member is unique (no repetition), and the members have such values that any number between 1 and the N*(N-1) (N is number of members) can be constructed by various combination (just adding) of them.
For Example: 1, 2, 4, 5
we have 1; 2; 2+1=3; 4, 4+1=5, 5; 4+2, 5+1=6; 4+2+1, 5+2=7; 5+2+1=8; 5+4=9; 5+4+1=10; 5+4+2=11, 5+4+2+1=12.
the main set has above conditions.
Now there is a set that is subset of above set for example A {1, 2, 4} or {1, 4} or any other subset, I like to know whether a desired number that is less than N*(N-1) (12 in this example) can be constructed by a subset of the set which was itself subset of main set.
For Example: Whether is there a subset of set A which its members add up to desired value ( for Example 6)?
Since the number of members of sets can be very large, dynamic programming need too much time. so I like to find out is it possible in first step and if it is possible then the program searches for that subset. if it isn't possible, goes to another subroutine.

thank you

bobbym · 2013-12-21 04:17:14

Hi;

Would it help to know all the possible sums beforehand?

kappa_am · 2013-12-21 07:55:53

Hi Dear Bobbym,
it's desirable not to calculate all possible sums, because it's cumbersome and time consuming. I wonder if there is a way to know whether a subset exists that add up to desired value without calculating all possibilities?

bobbym · 2013-12-21 09:18:19

The generating function can sometimes do that quite quickly. It does not calculate all sums but it does tell if a sum is possible and how many ways there are to make it. It does this for all possible sums automatically.

It may or may not be possible because I might not be smart enough to formulate it. That is why I need a typical problem. One that you might actually work on. A clear actual example, not a toy one, a real one.

That is if you would like a list of all possible sums. It is a little difficult to understand what a generating function does but how it does it is quite simple.

Math Is Fun Forum

#1 2013-12-20 07:02:44

A question about Knapsack problem (discrete math)

#2 2013-12-20 07:04:47

Re: A question about Knapsack problem (discrete math)

#3 2013-12-20 07:47:53

Re: A question about Knapsack problem (discrete math)

#4 2013-12-20 11:08:20

Re: A question about Knapsack problem (discrete math)

#5 2013-12-20 19:25:19

Re: A question about Knapsack problem (discrete math)

#6 2013-12-20 22:38:01

Re: A question about Knapsack problem (discrete math)

#7 2013-12-20 23:34:51

Re: A question about Knapsack problem (discrete math)

#8 2013-12-21 04:17:14

Re: A question about Knapsack problem (discrete math)

#9 2013-12-21 07:55:53

Re: A question about Knapsack problem (discrete math)

#10 2013-12-21 09:18:19

Re: A question about Knapsack problem (discrete math)

Board footer