Request for comments on a variation of packing problem

[rahul]

Given buffer of varying sizes, I have to combine them into one big
block of size MAX using min. number of individual buffer blocks.

Consider:
#define MAX 64
int a[LEN] = {30, 50, 20, 14, 30, 4, 19, 20, 11, 24};

The solution for this case will be
idx size
1 50
3 14

So, I will be combining 1 and 3 to obtain a block of 64 KB. Here is my
solution for this:
http://rahulkmr.pastebin.com/m68768ce1

IMO, the only solution to this problem involves generating all
combinations, filtering them on which one sums to MAX and then
selecting the combination with min. items. I can follow the greedy
approach, but I don't think it is going to yield any better results.

My solution is O(n^3). I would like to know if it can be further
optimized without convoluting it.


Rahul

 

[Nick Keighley]

Given buffer of varying sizes, I have to combine them into one big
block of size MAX using min. number of individual buffer blocks.

Consider:
#define MAX 64
int a[LEN] = {30, 50, 20, 14, 30, 4, 19, 20, 11, 24};

The solution for this case will be
idx                       size
1                          50
3                          14

So, I will be combining 1 and 3 to obtain a block of 64 KB. Here is my
solution for this:http://rahulkmr.pastebin.com/m68768ce1

IMO, the only solution to this problem involves generating all
combinations, filtering them on which one sums to MAX and then
selecting the combination with min. items. I can follow the greedy
approach, but I don't think it is going to yield any better results.

My solution is O(n^3). I would like to know if it can be further
optimized without convoluting it.

maybe try posting it in comp.programming they seem to like puzzles
like this

 

[Flash Gordon]

Given buffer of varying sizes, I have to combine them into one big
block of size MAX using min. number of individual buffer blocks.

Consider:
#define MAX 64
int a[LEN] = {30, 50, 20, 14, 30, 4, 19, 20, 11, 24};

The solution for this case will be
idx size
1 50
3 14

So, I will be combining 1 and 3 to obtain a block of 64 KB. Here is my
solution for this:http://rahulkmr.pastebin.com/m68768ce1

IMO, the only solution to this problem involves generating all
combinations, filtering them on which one sums to MAX and then
selecting the combination with min. items. I can follow the greedy
approach, but I don't think it is going to yield any better results.

My solution is O(n^3). I would like to know if it can be further
optimized without convoluting it.

Yours already looks convulted to me, possibly due to poor variable
naming and commenting. A variable named "num" is not overly helpful. In
any case, it does not work for all inputs. Try
int a[LEN] = {3, 5, 20, 14, 3, 4, 19, 2, 11, 24};
I get no output for this. I'm not going to debug it for the OP either,
since I would do something more sophisticated (IMHO) instead.

Then there is the memory leak in the function if it does not find an
answer, which would be a problem if the program was used for more than a
single run. It returns a null pointer without freeing the buffer it had
allocated.

maybe try posting it in comp.programming they seem to like puzzles
like this

I agree it's an algorithms, although slightly more interesting (to me)
than some of them.

When posting in comp.programming the OP should be rather more specific.
Is there a limit on the amount of memory a solution can use? What is the
importance of best case, worst case and average case? I can easily give
a solution which, in the best case, is O(n) giving all of the equal
shortest instances. If you only need one of the equal best solutions it
degenerates to O(1) for the simplest case. I'm guessing as the OPs
solution only every gives one (of multiple equally good) answers only
one is needed.

The OPs suggestion for the solution would work, it's just the
implementation does not so does not implement the solution suggested.

This is also one instance where defining the constraints and selecting
the right algorithm will have massively more impact than anything else.

I'll give the OP one hint and one question, trees might be useful,
especially if you do a breadth first build of the tree. Would sorting
the array of block sizes help, and if so in what cases?

To the OP, ask your question about the algorithm in comp.programming
with a more detailed description of what you think the solution is, and
more details on the constraints and which cases you want optimised. Then
re-implement it and post the code here.