Minimize String Puzzle
I am trying to write an algorithm to solve this puzzle:
The factory gets string in 18inch and 36inch sections. The customer can order 1 to 15 sections of string with each section greater than 0inch and less than 36inch. The factory want to minimize the number of 18inch and 36inch sections used to fill a customer order.The factory uses a machine to cut the string that removes 0.25inches of string every cut.
I need an algorithm that takes an array of customer sections and returns the number of 18inch and 36inch sections needed to fill the customer order.
Anyone have any ideas?
Thanks,
DeltaCoder
That's a [url= http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/cutting/]cutting stock[/url] problem, which is an NPC problem. For yourparticular case (n and 2n lengths) a heuristic might be applicable.kind regards,Jos
JosAHa at 2007-7-16 13:33:16 >
I need an algorithm that does the following.
Create all legal combinations.
ie: Customer wants 5, 16, 23 inch sections.
23
23+5
16
16+5
5
Create all legal combinations to complete order.
23, 16, 6
23, 16+5
23+5, 16
Determine the remainder from each combination.
23, 16, 6 -> 36-23 + 18-16 + 18-5 = 28
23, 16+5 -> 36-23 + 36-21 = 28
23+5, 16 -> 36-28 + 18-16 = 10
Chose the combination with the least remainder.
23+5, 16
Does anyone know of any algorithms to create the combinations of cuts or the combinations of complete orders?
Thanks,
DeltaCoder
I can't give you an exact pointer but if memory serves me correctly someone posted code that solves this same basic problem to this algorithms section sometime within the last 3 months. (Amazing how teachers assign the same problems over and over)
Unfortunately, given that the typical title that people give to their questions, like "ples help me" or "algorithm problem" the chance of your finding it (or my finding it again) by any search method other than just looking at every single entry in the algorithms section over the last several months are slim.
You may either grovel and look for the already coded solution, or you may think of how you would do this recursively.
Imagin that you are partway through the cutting process, you have some remainder chunks on the floor from previous cutting. You may either cut the next chunk from remainder piece number 0, or you may cut it from remainder piece number 1, ... or cut it from remainder piece number n-1, or you may cut it from a new 18 inch section or you may cut it from a new 36 inch section. At each stage those are you only choices so you make them all.
When you have no pieces left to cut, you can see how bad your remainder problem was, i.e. return the total scrap.
Recursively you are asking the question, "Where should I be cutting piece number j so that I can minimize the amount of scrap remaining when I cut all the rest of the pieces"
Thanks for the reply. Just to let you know, this is not an assigment (I am not a student.) it is merely a puzzle I want to solve.
Although recursion was my first thought, there exists some problems. I have to double check but I believe Java can handle recursion to level 15 (which is the maximum number of customer sections) but later I may want to have an unlimited amount of customer sections (Java recursion has a depth limit). (Not to mention I will have to also write this in ABAP which I'm new to and have been told that it doesn't support recursion.)
I do like the idea of recursion based on the limited choices during each step (ie: cut section from remainder, from new 18, from new 36) when recursion bottoms out store the remainder and the state. After all states have been computed sort and take minimum remainder state as winner.
> (Java recursion has a depth limit). (Not to mention> I will have to also write this in ABAP which I'm new> to and have been told that it doesn't support> recursion.)ABAP recursion: http://www.sapgenie.com/abap/code/chap1011.txt
> (Java recursion has a depth limit)It's called the stack size. It can be adjusted, although I've never had to do so in about 5.5 years of using Java.
> Anyone have any ideas?
This is typical integer linear programming problem as stated above and
it can be solved using the simplex algorithm.
> For your particular case (n and 2n lengths) a heuristic might
> be applicable.
I know that the definition of 'heuristic' is a bit blurry, but I think
that most people would agree on that a heuristic is a technique
designed to solve a problem that ignores whether the solution can be
proven to be correct ( http://en.wikipedia.org/wiki/Heuristic ).
Using this definition, all NP-complete problem instances do not need
to use a heuristic algorithm to be solved. The simplex algorithm is
not heuristic because if a solution is found, it is also proven to be
one of the optimal ones. It is common mistake to think that just
because a problem is NP-complete, all its instances will be hard to
solve. In many cases a polynomial time algorithm can solve a 'large'
subset of its instance domain.
parza at 2007-7-16 13:33:16 >
> > Anyone have any ideas?
>
> This is typical integer linear programming problem as
> stated above and it can be solved using the simplex algorithm.
Not by the simplex algorithm by itself (nor by an interior point algorithm
either). After a relaxation solution has been found a form of branch and
bound has to be applied to find the 'real' integer solution ...
> > For your particular case (n and 2n lengths) a heuristic might
> > be applicable.
> I know that the definition of 'heuristic' is a bit blurry, but I think
> that most people would agree on that a heuristic is a technique
> designed to solve a problem that ignores whether the solution can be
> proven to be correct ( http://en.wikipedia.org/wiki/Heuristic ).
>
> Using this definition, all NP-complete problem instances do not need
> to use a heuristic algorithm to be solved. The simplex algorithm is
> not heuristic because if a solution is found, it is also proven to be
> one of the optimal ones. It is common mistake to think that just
> because a problem is NP-complete, all its instances will be hard to
> solve. In many cases a polynomial time algorithm can solve a 'large'
> subset of its instance domain.
Of course the term 'heuristics' is vaguely defined at best; that's why the
fans switched to the term 'local search' ;-) but I don't really know if I
understand what you want to make clear: a simplex algorithm solves
the relaxation of the problem at hand (also see above) which can be a
long way to the real optimal solution ... as I wrote in my previous reply:
a heuristic might (or 'may') be applicable ...
kind regards,
Jos
JosAHa at 2007-7-16 13:33:16 >
> After a relaxation solution has been found a form of branch and
> bound has to be applied to find the 'real' integer solution ...
I was under the illusion that only a minor polynomial algorithm
was needed to go from the basic optimal solution provided by
Simplex to the final integer solution. I dusted of some school
books, and now I know better. Thanks.
> I don't really know if I understand what you want to make clear:
Because of my wrong assumption above, I thought you claimed that
the Simplex method was heuristic (under the given definition).
If we put the problem above a side, it is a common mistake to
think that all instances of a NP-complete problem is hard to
solve. The problem of solving a linear programming problem in
canonical form is NP-complete but Simplex solves 'most' instances
in polynomial time and Simplex is not unique when it comes to
this.
parza at 2007-7-16 13:33:16 >
> > After a relaxation solution has been found a formof branch and
> > bound has to be applied to find the 'real' integer solution ...
>
> I was under the illusion that only a minor polynomial algorithm
> was needed to go from the basic optimal solution provided by
> Simplex to the final integer solution. I dusted of some school
> books, and now I know better. Thanks.
You're welcome. Only those problems P(minimise cx w.r.t. Ax = b)
yield integer solutions where the matrix A is a so called unimodular
matrix. Problems such as the MCNF (Minimal Cost Network Flow)
and its derivatives are ideal examples of such matrices.
> > I don't really know if I understand what you want to make clear:
>
> Because of my wrong assumption above, I thought you claimed that
> the Simplex method was heuristic (under the given definition).
Ah, ok, comprendo.
> If we put the problem above a side, it is a common mistake to
> think that all instances of a NP-complete problem is hard to
> solve. The problem of solving a linear programming problem in
> canonical form is NP-complete but Simplex solves 'most' instances
> in polynomial time and Simplex is not unique when it comes to this.
Yes, this is completely true. The simplex algorithm (as well as the
Interior Point algorithm) run in polynomial time for 'average' problems.
This can still take a lot of time when, say, >= 1e6 variables and a lot of
constraints are involved ...
kind regards,
Jos
JosAHa at 2007-7-16 13:33:16 >
HiGuy I am stuck with this recursion ....I need the permutation of a String lets say "1234"I need "1234" ,"1243","1324","4123" and..repetion not allowed..anyone has any idea?
> I need the permutation of a String lets say "1234"I need
> "1234" ,"1243","1324","4123" and..repetion not allowed..
> anyone has any idea?
Why didn't you create a new thread? And why invade this one? It has nothing to do with your homework.
But here you go, all 24 solutions:
> Executing: "C:\...\Java\jdk1.5.0_02\bin\java.exe" Permutations
1234
2341
3412
4123
2314
3142
1423
4231
3124
1243
2431
4312
2134
1342
3421
4213
1324
3241
2413
4132
3214
2143
1432
4321
> Execution finished.
Hi
i didnt know how to start a new thread.I dont what homework u are talking about I am weak at recrsion and i am trying so many example.This is the one that iam stuck with the most.I am looking for an efficient algorithm .What you posted is i dont know ..its not the code i guess ..anyway thanks if u cant help
to permute n elements in an array.
For each of the n elements in the array, put that element in some fixed slot (like the last one at n-1 you can swap the element that you need into place) and then while that element is in place, permute the other n-1 elements.
Notice how permuting a group of size N is broken down into permuting a group of size N-1, something samller. This is how you write recursive functions.
Enjoy!
public class permutation {
public static void main(String[] args) {
int[]array={4,3,2,1};
for (int i : array) {
System.out.print(i+";");
}
System.out.println();
permutation(array,0,0);
}
public static void permutation(int[] array,int cur, int start){
if(cur >= array.length){
return;
}
else if(cur== array.length-1){
//next perm on next elem index
permutation(array, start+1, start+1);
}
else{
//go through each elem to gen perm
int[] newArray = new int[array.length];
fillarray(array,newArray,start,0);
int lastval = array[start];
newArray[array.length-1] = lastval;
for (int i : newArray) {
System.out.print(i+";");
}
System.out.println();
cur++;
permutation(newArray,cur, start);
}
}
public static void fillarray(int[] array,int[] newArray,int cur,int start){
if(cur >= array.length-1){
return;
}
else if(start<cur){
int val = array[start];
newArray[start]=val;
fillarray(array,newArray,cur,start+1);
}
else{
int val = array[cur+1];
newArray[cur] = val;
fillarray(array,newArray,cur+1,start+1);
}
}
4;3;2;1;
3;2;1;4;
2;1;4;3;
1;4;3;2;
1;3;2;4;
1;2;4;3;
1;2;3;4;
i cant get any more than that.on the right track?i dont think so.>
Need more help?Google "Permutations in Java" first link is http://www.cs.princeton.edu/introcs/23recursion/Permutations.java.html
