Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #37388

Re: Is there already an easy fit algorithm?

Newsgroups comp.lang.java.programmer
Date 2017-09-12 05:05 -0700
References <137a4648-a4a2-42f9-929e-129787f79650@googlegroups.com> <284544a2-9e8a-4150-a048-c8eb30ddda6a@googlegroups.com> <e326c7af-2371-471d-894d-b4f4ccbbba67@googlegroups.com> <op4tp1$ai6$1@dont-email.me> <uhkerch59h8c5o3p5vqvl90r4vrlp1llt0@4ax.com>
Message-ID <5bca0979-6dd1-40ed-94aa-d2e0705942c2@googlegroups.com> (permalink)
Subject Re: Is there already an easy fit algorithm?
From Eric Douglas <e.d.programmer@gmail.com>

Show all headers | View raw

On Monday, September 11, 2017 at 11:25:05 PM UTC-4, Gene Wirchenko wrote:
> >Integer knapsack is NP-complete. The greedy algorithm doesn't work. 
> >Imagine your capacity is 10 units, and you have cubes of size 7, 6, and 
> >4. Your algorithm says you can only fit the 7 cube, but you can fit 
> >cubes 6 and 4.
> 
>      Bad example since the second truck will get 6 and 4.  The
> solution is optimum though accidentally so.
> 
>      Here is an example that illustrates the point:
> 
>      Capacity is 10.  You have units 5, 4, 3, 3, 3, 2.
> 
>      Greedy gets [5, 4] then [3, 3, 3] then [2] requiring 3 loads.
> 
>      Better is [5, 3, 2] then [4, 3, 3] requiring 2 loads.
> 
> 
>      Your use of the term "cubes" is unclear.  Do you mean the
> gemoetric object or cubic units of measure?
> 
> Sincerely,
> 
> Gene Wirchenko

My final algorithm puts those in 3 buckets.  The first gets 4 and 5, second gets 3, 3, 3, third gets 2.  While ultimately they should fit in 2 buckets with a 5, 3, 2 and a 4, 3, 3, it is close.  If your fit is not exact it may end up needing 3 buckets anyhow.  Unless your size numbers are significantly larger than your items or your items are some kind of liquid/gel, it'll be hard to get exact fit..

Of course in real world it also helps that the bucket is much larger than 10.  You're fitting numbers of 10 to 350 into buckets of 2800..

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-08 05:05 -0700
  Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-08 07:38 -0700
    Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-08 08:34 -0700
    Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-08 11:36 -0700
      Re: Is there already an easy fit algorithm? Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2017-09-10 22:52 -0400
        Re: Is there already an easy fit algorithm? Gene Wirchenko <genew@telus.net> - 2017-09-11 20:24 -0700
          Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 05:05 -0700
          Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 05:11 -0700
            Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-12 10:31 -0700
              Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 10:52 -0700
                Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-12 12:43 -0700
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 13:02 -0700
                Re: Is there already an easy fit algorithm? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-09-12 17:08 -0400
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 05:21 -0700
                Re: Is there already an easy fit algorithm? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-09-13 12:49 -0400
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 11:13 -0700
                Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-13 14:24 -0700
                Re: Is there already an easy fit algorithm? Arne VajhĂžj <arne@vajhoej.dk> - 2017-09-13 20:35 -0400
                Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-14 11:26 -0700
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-14 11:53 -0700
                Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-14 19:49 +0000
                Re: Is there already an easy fit algorithm? lewbloch@gmail.com - 2017-09-14 14:38 -0700
                Re: Is there already an easy fit algorithm? Arne VajhĂžj <arne@vajhoej.dk> - 2017-09-14 20:34 -0400
                Re: Is there already an easy fit algorithm? Andreas Leitgeb <avl@logic.at> - 2017-09-15 09:22 +0000
                Re: Is there already an easy fit algorithm? Arne VajhĂžj <arne@vajhoej.dk> - 2017-09-15 20:03 -0400
                Re: Is there already an easy fit algorithm? Gene Wirchenko <genew@telus.net> - 2017-09-19 21:16 -0700
                Re: Is there already an easy fit algorithm? Arne VajhĂžj <arne@vajhoej.dk> - 2017-09-20 08:58 -0400
                Re: Is there already an easy fit algorithm? leif.roar@dimnakorr.com - 2017-09-18 04:14 -0500
                Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-12 21:50 +0000
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 05:12 -0700
                Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-13 13:07 +0000
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 06:33 -0700
                Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-13 16:37 +0000
                Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-13 10:36 -0700
                Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-13 18:54 +0000
            Re: Is there already an easy fit algorithm? Gene Wirchenko <genew@telus.net> - 2017-09-19 21:21 -0700
          Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 07:32 -0700
            Re: Is there already an easy fit algorithm? Eric Douglas <e.d.programmer@gmail.com> - 2017-09-12 08:02 -0700
  Re: Is there already an easy fit algorithm? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-09-12 11:47 -0400
  Re: Is there already an easy fit algorithm? Martin Gregorie <martin@address-in-sig.invalid> - 2017-09-15 10:27 +0000

csiph-web