Re: Optimal number of sheets

• To: mathgroup at smc.vnet.net
• Subject: [mg58365] Re: [mg58324] Optimal number of sheets
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Tue, 28 Jun 2005 21:56:59 -0400 (EDT)
• References: <200506280913.FAA05137@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Erb, John wrote:
> Hello,
>
> On a given occasion, I wish to create different thicknesses of a
> material, ranging
> say, for example, from 1 cm to 25 cm, in increments of 1 cm.
>
> How can I, using Mathematica, determine the minimum number
> of sheets of material I need?
> The material comes in thicknesses of 1, 2, 3, 4, & 7 cm.
>
> Thank you,
> John C. Erb
> email:  John_C_Erb at prodigy.net
>
>
> Saint Luke's Health System Confidentiality Notice:
> [...]

For this list of thicknesses the best method is a greedy algorithm. Use
as many of the 7 cm sheets as possible, then 4 cm, etc. One way to do
this in Mathematica is with FoldList. The code below does no error
checking and assumes the thicknesses are arranged in increasing order.

thicknesses = {1, 2, 3, 4, 7};

sheets[ll_List, n_] := Module[
{val=n, q, r, vals},
vals = Reverse[Rest[FoldList[
(q = Quotient[val,#2]; val = val - q*#2; q)&,
0, Reverse[ll]]]];
{Total[vals], vals}
]

In[18]:= InputForm[Map[sheets[thicknesses,#]&, Range[25]]]

Out[18]//InputForm=
{{1, {1, 0, 0, 0, 0}}, {1, {0, 1, 0, 0, 0}}, {1, {0, 0, 1, 0, 0}},
{1, {0, 0, 0, 1, 0}}, {2, {1, 0, 0, 1, 0}}, {2, {0, 1, 0, 1, 0}},
{1, {0, 0, 0, 0, 1}}, {2, {1, 0, 0, 0, 1}}, {2, {0, 1, 0, 0, 1}},
{2, {0, 0, 1, 0, 1}}, {2, {0, 0, 0, 1, 1}}, {3, {1, 0, 0, 1, 1}},
{3, {0, 1, 0, 1, 1}}, {2, {0, 0, 0, 0, 2}}, {3, {1, 0, 0, 0, 2}},
{3, {0, 1, 0, 0, 2}}, {3, {0, 0, 1, 0, 2}}, {3, {0, 0, 0, 1, 2}},
{4, {1, 0, 0, 1, 2}}, {4, {0, 1, 0, 1, 2}}, {3, {0, 0, 0, 0, 3}},
{4, {1, 0, 0, 0, 3}}, {4, {0, 1, 0, 0, 3}}, {4, {0, 0, 1, 0, 3}},
{4, {0, 0, 0, 1, 3}}}

Here is a general approach that does not assume the greedy method will
be optimal (or even that it will deliver a solution since, in general,
it might not). Use Minimize, give appropriate constraints, and that's
all that need be done.

mults = Array[x,5];

In[21]:= InputForm[Table[
{#[[1]], mults /. #[[2]]}& [
Minimize[{Total[mults], {mults.thicknesses==j,
{j,25}]]

Out[21]//InputForm=
{{1, {1, 0, 0, 0, 0}}, {1, {0, 1, 0, 0, 0}}, {1, {0, 0, 1, 0, 0}},
{1, {0, 0, 0, 1, 0}}, {2, {0, 1, 1, 0, 0}}, {2, {0, 1, 0, 1, 0}},
{1, {0, 0, 0, 0, 1}}, {2, {0, 0, 0, 2, 0}}, {2, {0, 1, 0, 0, 1}},
{2, {0, 0, 1, 0, 1}}, {2, {0, 0, 0, 1, 1}}, {3, {0, 0, 0, 3, 0}},
{3, {0, 0, 2, 0, 1}}, {2, {0, 0, 0, 0, 2}}, {3, {0, 0, 0, 2, 1}},
{3, {0, 1, 0, 0, 2}}, {3, {0, 0, 1, 0, 2}}, {3, {0, 0, 0, 1, 2}},
{4, {0, 0, 0, 3, 1}}, {4, {0, 0, 2, 0, 2}}, {3, {0, 0, 0, 0, 3}},
{4, {1, 0, 0, 0, 3}}, {4, {0, 1, 0, 0, 3}}, {4, {0, 0, 1, 0, 3}},
{4, {0, 0, 0, 1, 3}}}

So when is the greedy method guaranteed to work? A sufficient condition
is that the input have an arithmetic progression
{1,3,7,...,2*(n-1)+1,...}. Here is a math question: What would be the
necessary condition that it work? Offhand I don't know though I suspect
it is something simple.

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: Re: Minimal maximum eigenvalue in closed form?
• Next by Date: Re: Minimal maximum eigenvalue in closed form?
• Previous by thread: Optimal number of sheets
• Next by thread: Re: Optimal number of sheets