http://mathoverflow.net/questions/57371/find-all-maximal-subsets-of-a-set-of-integers-whose-sum-does-not-exceed-a-number
actual question is this.
On Sat, Aug 27, 2011 at 9:56 AM, rahul sharma wrote:
> yeah i wen first post answer i said it is for finding sum=k;
> n just add one more condition in
yeah i wen first post answer i said it is for finding sum=k;
n just add one more condition in loop for finding wrote:
> It's not knapsack in knapsack we find max or min subset here we have to
> find all subsets <=k not just one which is min or max , so I guess we have
> to form all subsets and ch
It's not knapsack in knapsack we find max or min subset here we have to find
all subsets <=k not just one which is min or max , so I guess we have to
form all subsets and check their sum hence the algoritm will be 0(2^n) where
n is number of elements in the set ,
please correct me if i am wrong or
The 0-1 knapsack problem is still the knapsack problem.
Don
On Aug 26, 1:55 pm, Piyush Grover wrote:
> it's similar to knapsack but not the same. In knapsack, types of items are
> limited and we play on the quantity of each item.
> Here each element will come once in the subset.
>
> On Fri, Aug 2
it's similar to knapsack but not the same. In knapsack, types of items are
limited and we play on the quantity of each item.
Here each element will come once in the subset.
On Fri, Aug 26, 2011 at 11:49 PM, Don wrote:
> @rahul
> Your code will only find pairs which sum to k. The problem is to fi
@rahul
Your code will only find pairs which sum to k. The problem is to find
a subset of as many elements in the array as required to sum as close
as possible to k.
It is a well-known problem and after years of study, no polynomial
solution is known. There are reasonably fast solutions for small
in
yes it will
return in c return 1 value at tym...
ijust given the code snipetjust modify it..store trhm in some
other array like thebut it will
On Aug 26, 11:02 pm, Piyush Grover wrote:
> @rahul...I'm unsure if your algo returns all the subsets.
>
> On Fri, Aug 26, 2011 at 11:24 PM
@rahul...I'm unsure if your algo returns all the subsets.
On Fri, Aug 26, 2011 at 11:24 PM, rahul sharma wrote:
> yeah can be done in poly tym also...but we dnt knw whether we have
> unsorted arryit is possible in sorted array.
>
> On Aug 26, 10:52 pm, Don wrote:
> > This is the knapsack pro
yeah can be done in poly tym also...but we dnt knw whether we have
unsorted arryit is possible in sorted array.
On Aug 26, 10:52 pm, Don wrote:
> This is the knapsack problem.
> Find a polynomial-time solution and you will be a hero.
> Don
>
> On Aug 26, 12:43 pm, Piyush Grover wrote:
>
>
>
This is the knapsack problem.
Find a polynomial-time solution and you will be a hero.
Don
On Aug 26, 12:43 pm, Piyush Grover wrote:
> Here is a problem:
>
> Given an array of size n. Find all the MAXIMAL subsets whose sum is <= K.
> The solution is not a concern, the optimization is required.
>
>
take h as array/has table as max element of a as size.
just a psecudeocde.
for(i=0;i wrote:
> Here is a problem:
>
> Given an array of size n. Find all the MAXIMAL subsets whose sum is <= K.
> The solution is not a concern, the optimization is required.
>
> -piyush
--
You received this messag
11 matches
Mail list logo
