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

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

Re: Is there already an easy fit algorithm?

Show all headers | View raw

On 9/8/2017 2:36 PM, Eric Douglas wrote:
> Now I believe the cubes need to be input sorted largest to smallest
> so I'll need to ensure that, and I need to update it for dynamic
> input to handle a variable number of items with quantities and cubes,
> matching up to the dynamic output to tell which items were selected
> rather than just their cubes.

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.

-- 
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

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