Box packing problem

[Horizon]

Hello,

I'm looking to create a Just BASIC program that can tell me the most efficient method of packing my items into boxes. I have 5 sizes of boxes and each box can hold the following number of items in them. Dimensions are unimportant as each item flits a slot in the box perfectly:

Box type A holds 8 items
Box type B holds 12 items
Box type C holds 16 items
Box type D holds 24 items 
Box type E holds 32 items

The challenge I'm facing is to find the lowest number of boxes for the order from any quantity of items up to 1024. Of course odd numbers will create spaces in boxes (which is unavoidable) and numbers of items that don't divide exactly into the types boxes available (10 items being a good example, that leaves 2 empty slots in box type 'B').

1:1 is not a problem (a matched condition)

    if items = box_type then [one box of that type required]

This of course would be the first item and box comparison in the program. When we have a larger number of items is where it gets more interesting...

    if items / 2 = box_type without any remainders then [two boxes required of that type]

Perhaps a practical approach is how may time can you divide you items in to the largest box type (if your number is less than one then step down to the next box size and re calculate). Of course it's not practical to continue in this fashion.

So, the next steps are creating a formula (rules) that can be applied to any number of items entered.

I don't profess to have a great deal of mathematical skills but, a point in the right direction leads the way to discovery.

Any insight would be very welcome.

[tsh73]

How about just picking as much of big boxes as possible?
Also since goal is "lowest number of boxes" we could just ignore all amaller boxes. Because box count will be the same!
so N/32, rounded Up

[Rod]

Yeah I am not sure we have the full problem description as yet. Is the supply of boxes limited in any way? This just fills the largest boxes first. So it probably isn't the correct answer but it will give us something to discuss.

box(1)=(32)
box(2)=(24)
box(3)=(16)
box(4)=(12)
box(5)=(8)
for i= 750 to 1024
packtotal=0
items=i
n=1
while items>0
  'fill the largest boxes first
   if items>=box(n) then
       box=int(items/box(n))
       items=items-box*box(n)
       packtotal=packtotal+box*box(n)
       print "Box type ";n;" No boxes ";box;" Total packed ";packtotal;" Remaining ";items
   end if
   n=n+1
   'mop up the remainder
   if items <=8 then
       box=1
       packtotal=packtotal+items
       items=0
       print "Box type ";n;" No boxes ";box;" Total packed ";packtotal;" Remaining ";0
   end if
wend
print
next


[Horizon]

I really appreciate the help on this and expanding on Rod's example code I think we're nearly at the solution:


[main.inputLoop]

   box(1)=(32) 'box B1
   box(2)=(24) 'box B2
   box(3)=(16) 'box B3
   box(4)=(12) 'box B4
   box(5)=(8)  'Box B1

   cls
   input "Please enter number of items: ";items
   packtotal=0
   n=1

   if items <9 then [onebox]

   while items>0
  'fill the largest boxes first
   if items>=box(n) then
       box=int(items/box(n))
       items=items-box*box(n)
       packtotal=packtotal+box*box(n)
       print "B";n;" * ";box;" packed ";packtotal;" items remaining ";items
   end if
   n=n+1
   if items = 0 then [again]
   'mop up the remainder
   if items <=8 then
       box=1
       packtotal=packtotal+items
       items=0
       print "B";n;" * ";box;" packed ";packtotal;" items remaining ";items
   end if
   wend

[again]
   input "Calculate another? Y/N: "; answer$
   if answer$ <> "n" then [main.inputLoop]
   print "End."
   end

[onebox]
   print "B5 * 1 packed ";items;" items remaining ";0
   goto [again]


However, odd things happen when the items input is between 9 and 11? Other combinations too?

[plus]

Along with minimizing the number of boxes, I'd try to minimize the number of empty slots. Why use more box than you need?

For items = 1 To 100
   print "For "; items; " items:  ";
   If items >= 32 Then
       print "32 boxes = "; Int(items / 32); ", "; 32 * Int(items / 32); " items";
   End If
   r = items Mod 32
   If r <= 8 Then
       If r > 0 Then Print " 8 box "; r; " items";
   Else
       If r <= 12 Then
           Print " 12 box "; r; " items";
       Else
           If r <= 16 Then
               Print " 16 box "; r; " items";
           Else
               If r <= 24 Then
                   Print " 24 box "; r; " items";
               Else
                   If r < 32 Then
                       Print " 32 box "; r; " items";
                   End If
               End If
           End If
       End If
   End If
   Print "."
   'If items Mod 20 = 0 Then Print "zzz": Sleep
Next
Print " and so on..."


After a 100 you should get the picture. ;-))

[Rod]

My solution? Minimum order is 24 units. One box, no waste, but that's thinking out the box.

[plus]

Here is same thing with all those IF blocks cleaned out using Select Case:
For items = 1 To 100
   print "For "; items; " items:  ";
   If items >= 32 Then
       print "#32 box use "; Int(items / 32); ", "; 32 * Int(items / 32); " items";
   End If
   r = items mod 32
   select case
       case (r = 0)
       case r <= 8:  Print " #8 box "; r; " items";
       case r <= 12: Print " #12 box "; r; " items";
       case r <= 16: Print " #16 box "; r; " items";
       case r <= 24: Print " #24 box "; r; " items";
       case r < 32:  Print " #32 box "; r; " items";
     end select
   Print "."
Next
Print " and so on..."



[tsh73]

Here is same thing with all those IF blocks cleaned out using Select Case:

Looks really neat