Challenge #52: Solving the Knapsack Problem

[GeneR]

A link to the last challenge is HERE.

The knapsack problem: 

There are 5 boxes of varying weights and dollar amounts - which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg?

From a challenge standpoint, which combination of box/boxes is most optimal if you were only allowed 1 box in the backpack? 2 boxes in the backpack? 3 boxes in the backpack? or 4 boxes in the backpack?

Output 1: details the number of boxes and total $ without going over 15kg.

Output 2: details the specific blocks per batch.

I have included spatial objects as part of the input should you want to use a location optimizer macro as part of the solution.  The new prescriptive simulation tools may also be a good choice for a solution.  We are looking forward to seeing the solutions you come up with. 

Please don't feel constrained by the example output, your solution may be better!  I am looking forward to seeing your solutions in this new more interactive forum.

[mceleavey]

I wanted to calculate this using the simple tools, to show it can be done without writing anything complex.

To begin with, I created a cartesian join to produce all possible combinations of boxes. This, however, results in a combination of 1 and 2 being treat differently to 2 and 1. Also, we now have combinations of the same box.

I then used simple formulae to remove those combinations of the same box.

This left me with only the combinations including non-unique strings in different orders to remove:

I did this by transposing the records, ordering them by box number, and cross-tabbing back. This made 123 and 321 the same, which could then be filtered out using the unique tool.

Following this it was simple to filter out those combinations over 15kg, and use the sample tool to take the highest value of each combination by number of boxes:

[alex]

Taking a break from my fractional CFO work and getting back to some Alteryx work.  I never got around to posting my solution for this.  I built this out without a macro and only 2 joins and some simple formulas.  It also doesn't require the formulas to have the exact number of boxes to work.  The only drawback is that in only works up to 9 boxes(unique items).  I assigned each box a unique id number and figured out how many combinations there could be, including duplicates, having each value in any combination or order (1,2,3 and 3,2,1 are different).  That process gave me a row for every value from 1 to 54,321 (5,4,3,2,1).  I then split the values into a column for each separate number of the value and transposed the data.  I filtered out zeros, nulls, and numbers greater than 5 (since there were only 5 boxes) along the way.  I used a multi-row tool to figure out what rows to mark for deletion based on if a row had more than 1 of each digit.  Filtered to unique values, split them up to have box id's to join to the original data set.  From that point the remaining workflow from there is pretty simple and self explanatory if you want to download my solution to view the exact mechanics.  The workflow is shown below.

[SeanAdams]

This challenge also seems to have spurred some very divergent solutions.

My approach was a bit different to the others posted above.   Looked at the solution posted and although it works for this data set, I'm not sure if it will work for all data-sets because it's essentially a greedy-fill single-pass algo (which is a very useful shortcut, but will miss some options thrown up by exploding the full solution space.

Spoiler

- Built an iterative macro to progressively create experiments with 1; then 2; then 3.... boxes.   Because this is iterative, it will work for any number of boxes, and only stops when it runs out of results.
- However, because this was built as an iterative macro, had to jump through some pretty ridiculous hoops to create the data at each iteration.
- Used many of the same ideas as @alex and @mceleavey to remove experiments over 15kg, experiments which are reordered versions of themselves (e.g. 1-2 and 2-1), and experiments which reuse the same box many times.

So - although we've solved this using standard means - I'm now very curious to see how to do this using a location optimizer - so I'm keeping this on my own personal list as unsolved for now :-)

[mceleavey]

Yes, I feel I have unfinished business here too.

[SeanAdams]

Turns out that doing this with location optimization is MASSIVELY easier than doing it the other way.

I've updated my solution file so now it has both solution types in one file

Spoiler

Location optimizer has a setting for how many nodes to use - so all you need to do is build a scoring function.

[estherb47]

Feel like I cheated a bit by using the Optimization tool in Prescriptive, but it just makes things so easy....

Spoiler

Spoiler

To optimize with restrictions on the number of boxes, I just changed the last constraint to be ==1 for one box, ==2 for 2, etc.

[mceleavey]

That's not cheating at all, that's just using Alteryx as intended!
Well done for using the new tool. Using new tools makes my geek senses tingle.
#needtogetoutmore

[NicoleJohnson]

My solution!! Finished this a while ago, but apparently forgot to post it! Thanks for counting for me @JoeM... this one is #70 for me! And a good thing he caught me too, because I'm pretty proud of this one! I created an app where you can select the number of boxes for the knapsack, and the weight limit you want to use, and it will run through the various combinations to find the highest $ value combo. Believe it should work for any # of boxes/weight limits. Cheers!

Spoiler

Probably made this 10 times harder than I needed to with the dynamic app parameters, but it worked :) Good app practice!

[LordNeilLord]

Finally got there this one...messy workflow :(

Spoiler