Best use of steel bar cut for mechanical study

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}}


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.


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}}