[Date Index]
[Thread Index]
[Author Index]
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,
Element[mults,Integers], Thread[mults>=0]}}, mults]],
{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**
| |