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

Improve this question
$\endgroup$
7
  • 8
    $\begingroup$ This is known as the knapsack problem and there is a built-in function solve it, KnapsackSolve. $\endgroup$
    – C. E.
    Jan 23, 2019 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, 2019 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, 2019 at 16:46
  • 2
    $\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, 2019 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, 2019 at 20:47

3 Answers 3

Reset to default
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}}

Improve this answer
$\endgroup$
7
$\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.

Improve this answer
$\endgroup$
7
$\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}}

Improve this answer
$\endgroup$
4
  • $\begingroup$ Very good supplement; please take into account, however, that every length must be present at least once. $\endgroup$
    – rmw
    May 29, 2019 at 12:51
  • $\begingroup$ @rmw the question does not state this restriction. $\endgroup$
    – Roman
    May 29, 2019 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, 2019 at 13:13
  • $\begingroup$ Excellent, I'm not aware of KnappsackSolve. $\endgroup$
    – rmw
    May 30, 2019 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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