12
$\begingroup$

I have available a steel bar with length of 3000 mm.

I intend to get the best use of cutting out of this bar.

I need to cut this steel bar in the following lengths: 230mm, 260mm, 320mm, 350mm and 650mm.

enter image description here

How to get cut options "close" to the length of 3000 mm.

Example:

230 + 230 + 260 + 260 + 320 + 320 + 350 + 350 + 650;

-> 2970

I have the code below. I know I will have to use the "Nearest" function, but I am not able to apply it:

lista={230, 260, 320, 350, 650};
resultados=Join@@DeleteCases[IntegerPartitions[#,{1,\[Infinity]},lista]&/@Range[3000],{}];
And@@Thread[Total/@resultados<=3000];
contagem=Map[Lookup[Counts[#],lista,0]&,resultados];
contagem//Short

In the my example, i get groups that are smaller that 3000, but wish the values that are "nearest" of the value of 3000

$\endgroup$
  • 7
    $\begingroup$ This is known as the knapsack problem and there is a built-in function solve it, KnapsackSolve. $\endgroup$ – C. E. Jan 23 at 11:34
  • $\begingroup$ Almost this. There are several combinations possible of cut with these lengths that added are "close" of 3000 $\endgroup$ – LCarvalho Jan 23 at 11:43
  • $\begingroup$ @C.E. KnapsackSolve[{230, 260, 320, 350, 650}, 3000] gives me {13, 0, 0, 0, 0}, which only has total cost 2990. I realize large knapsack problems might be difficult, but surely the algorithm should find one of the maximal answers for this small example... any idea if I'm doing something wrong? $\endgroup$ – MassDefect Jan 23 at 16:46
  • 1
    $\begingroup$ @C.E.: The knapsack problem maximizes the number of elements selected from the set subject to the constraint that the total cost is less than the given value. (More generally, each item has a "payoff" as well as a cost, and if you don't specify the payoffs, Mathematica assumes them all to be 1, so the total payoff is the number of elements in the set.) Given this, it's not surprising that MM finds a solution where you cut the bar into as many small pieces as possible. ... $\endgroup$ – Michael Seifert May 28 at 20:43
  • 3
    $\begingroup$ ... If you set the costs equal to the payoffs (KnapsackSolve[{{230, 230}, {260, 260}, {320, 320}, {350, 350}, {650, 650}}, 3000]), you get the solution {10, 0, 0, 2, 0}, which has total cost (and payoff) 3000. $\endgroup$ – Michael Seifert May 28 at 20:47
16
$\begingroup$
x = {x1, x2, x3, x4, x5};
Maximize[{x.lista, x.lista <= 3000, ## & @@ Thread[x >= 0]}, x, Integers]

{3000, {x1 -> 0, x2 -> 0, x3 -> 5, x4 -> 4, x5 -> 0}}

If you have to use at least one of each piece:

Maximize[{x.lista, x.lista <= 3000, ## & @@ Thread[x >= 1]}, x, Integers]

{3000, {x1 -> 2, x2 -> 1, x3 -> 4, x4 -> 1, x5 -> 1}}

All solutions that use all of 3000mm:

FrobeniusSolve[lista, 3000]

{{0, 0, 0, 3, 3}, {0, 0, 5, 4, 0}, {0, 1, 2, 6, 0}, {0, 4, 3, 1, 1}, {0, 5, 0, 3, 1}, {1, 0, 1, 7, 0}, {1, 2, 5, 0, 1}, {1, 3, 2, 2, 1}, {2, 1, 4, 1, 1}, {2, 2, 1, 3, 1}, {3, 0, 3, 2, 1}, {3, 1, 0, 4, 1}, {4, 3, 0, 0, 2}, {4, 8, 0, 0, 0}, {6, 0, 1, 0, 2}, {6, 5, 1, 0, 0}, {7, 4, 0, 1, 0}, {8, 2, 2, 0, 0}, {9, 1, 1, 1, 0}, {10, 0, 0, 2, 0}}

Or use IntegerPartitions as follows:

Map[Lookup[Counts[#], lista, 0] &, IntegerPartitions[3000, All, lista]]

{{0, 0, 0, 3, 3}, {6, 0, 1, 0, 2}, {4, 3, 0, 0, 2}, {3, 1, 0, 4, 1}, {2, 2, 1, 3, 1}, {0, 5, 0, 3, 1}, {3, 0, 3, 2, 1}, {1, 3, 2, 2, 1}, {2, 1, 4, 1, 1}, {0, 4, 3, 1, 1}, {1, 2, 5, 0, 1}, {1, 0, 1, 7, 0}, {0, 1, 2, 6, 0}, {0, 0, 5, 4, 0}, {10, 0, 0, 2, 0}, {9, 1, 1, 1, 0}, {7, 4, 0, 1, 0}, {8, 2, 2, 0, 0}, {6, 5, 1, 0, 0}, {4, 8, 0, 0, 0}}

You can also use Solve and Reduce:

x /. Solve[{x.lista == 3000, ## & @@ Thread[x >= 0]}, x, Integers]
Reduce[{x.lista == 3000, ## & @@ Thread[x >= 0]}, x, Integers][[All, All, -1]] /. 
 Or | And -> List

{{0, 0, 0, 3, 3}, {0, 0, 5, 4, 0}, {0, 1, 2, 6, 0}, {0, 4, 3, 1, 1}, {0, 5, 0, 3, 1}, {1, 0, 1, 7, 0}, {1, 2, 5, 0, 1}, {1, 3, 2, 2, 1}, {2, 1, 4, 1, 1}, {2, 2, 1, 3, 1}, {3, 0, 3, 2, 1}, {3, 1, 0, 4, 1}, {4, 3, 0, 0, 2}, {4, 8, 0, 0, 0}, {6, 0, 1, 0, 2}, {6, 5, 1, 0, 0}, {7, 4, 0, 1, 0}, {8, 2, 2, 0, 0}, {9, 1, 1, 1, 0}, {10, 0, 0, 2, 0}}

$\endgroup$
6
$\begingroup$
lst = {230, 260, 320, 350, 650};
vars = {c1, c2, c3, c4, c5};
eq = Inner[Times, lst, vars, Plus]

(sol = FindInstance[eq == 3000 && vars > 0, vars, Integers, 10]) // Column
{c1 -> 1, c2 -> 3, c3 -> 2, c4 -> 2, c5 -> 1}
{c1 -> 2, c2 -> 1, c3 -> 4, c4 -> 1, c5 -> 1}
{c1 -> 2, c2 -> 2, c3 -> 1, c4 -> 3, c5 -> 1}

eq /. sol
{3000, 3000, 3000}

or with FrobeniusSolve

fs = FrobeniusSolve[lst, 3000];
Take[fs, #] & /@ Position[Not@MemberQ[#, 0] & /@ fs, True]
{{{1, 3, 2, 2, 1}}, {{2, 1, 4, 1, 1}}, {{2, 2, 1, 3, 1}}}

Thus all possibilities are determined to divide a steel rod in the predetermined lengths, each partial length must be present at least once and the sum of the partial lengths again 3000 mm results.

$\endgroup$
6
$\begingroup$

As we cannot be guaranteed that the combined length of pieces will be equal to the length of the original bar, to be most general I would combine @MichaelSeifert's comments on KnapsackSolve with one of @kglr's solutions. First, use KnapsackSolve to find out what the maximum possible combined length is,

lista = {230, 260, 320, 350, 650};
T = 3000;
kn = KnapsackSolve[Transpose[{lista, lista}], T]

{4, 8, 0, 0, 0}

kn.lista

3000

Then use the combined length of this exemplary maximal solution, kn.lista (which is equal to T=3000 in this case, but may be smaller in general), to find all solutions with this length: any of @kglr's solution will work, and I'll pick the simplest:

FrobeniusSolve[lista, kn.lista]

{{0, 0, 0, 3, 3}, {0, 0, 5, 4, 0}, {0, 1, 2, 6, 0}, {0, 4, 3, 1, 1}, {0, 5, 0, 3, 1}, {1, 0, 1, 7, 0}, {1, 2, 5, 0, 1}, {1, 3, 2, 2, 1}, {2, 1, 4, 1, 1}, {2, 2, 1, 3, 1}, {3, 0, 3, 2, 1}, {3, 1, 0, 4, 1}, {4, 3, 0, 0, 2}, {4, 8, 0, 0, 0}, {6, 0, 1, 0, 2}, {6, 5, 1, 0, 0}, {7, 4, 0, 1, 0}, {8, 2, 2, 0, 0}, {9, 1, 1, 1, 0}, {10, 0, 0, 2, 0}}

This method will work even if we start, for example, with T=3001 which has no solution. It will find a maximum possible length of 3000, and continue in the same way.


If we need at least $M$ pieces of each length (@rmw suggests $M=1$), we can first cut off $M$ pieces of each length from the bar, and then use the above algorithm on what's left:

lista = {230, 260, 320, 350, 650};
T = 3000;
M = 1;
kn = KnapsackSolve[Transpose[{lista, lista}], T - M*Total[lista]]

{1, 0, 3, 0, 0}

kn.lista

1190

FrobeniusSolve[lista, kn.lista] + M

{{1, 3, 2, 2, 1}, {2, 1, 4, 1, 1}, {2, 2, 1, 3, 1}}

$\endgroup$
  • $\begingroup$ Very good supplement; please take into account, however, that every length must be present at least once. $\endgroup$ – rmw May 29 at 12:51
  • $\begingroup$ @rmw the question does not state this restriction. $\endgroup$ – Roman May 29 at 13:04
  • 2
    $\begingroup$ @rmw it's trivial to add this restriction: just cut off one piece of each length, then apply this algorithm to what's left of the bar. $\endgroup$ – Roman May 29 at 13:13
  • $\begingroup$ Excellent, I'm not aware of KnappsackSolve. $\endgroup$ – rmw May 30 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.