Services & ResourcesWolfram ForumsMathGroup Archive

[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

• References:
  • Optimal number of sheets
    • From: "Erb, John" <jerb@saint-lukes.org>