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

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

Re: Is there already an easy fit algorithm?

Show all headers | View raw

On Friday, September 8, 2017 at 10:38:42 AM UTC-4, lewb...@gmail.com wrote:
> This is one variant of the "Knapsack Problem", which is well documented. How simple your variant is depends on things like whether the cubes are al the same size, whether there's an emphasis on not splitting loads for a particular product, whether the profit differs between products, whether they all go to the same destination, ... You haven't told us the details.
> 
> Research it. It's a standard problem.

ok, I think I got a version that works.

public class Knapsack {

     private final float[] arr;
     private final ArrayList<Float> retArr = new ArrayList<>();

     public Knapsack(final float[] cubes) {
          arr = cubes;
     }

     public boolean fitsOnTruck(final float truckCubes, final int pick) {
          if (pick == arr.length) {
               return true;
          }
          if (arr[pick] < truckCubes) {
               final boolean r = fitsOnTruck(truckCubes - arr[pick], pick + 1);
               if (!r) {
                    return fitsOnTruck(truckCubes, pick + 1);
               } else {
                    retArr.add(arr[pick]);
                    return true;
               }
          } else if (arr[pick] > truckCubes) {
               return fitsOnTruck(truckCubes, pick + 1);
          } else {
               retArr.add(arr[pick]);
               return true;
          }
     }

     public static void main(final String[] args) {
          final Knapsack rk = new Knapsack(new float[] { 16.5f, 15.1f, 2.6f, 2.6f });
          if (rk.fitsOnTruck(35f, 0)) {
               System.out.println("Success ");
               for (int i = 0; i < rk.retArr.size(); i++) {
                    System.out.println(rk.retArr.get(i));
               }
          }
          
     }
}

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.

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