topic Re: Challenge #52: Solving the Knapsack Problem in Weekly Challenges

Challenge #52: Solving the Knapsack Problem

GeneR — Tue, 13 Sep 2022 19:02:46 GMT

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.

Re: Challenge #52: Solving the Knapsack Problem

mceleavey — Tue, 17 Jan 2017 12:19:18 GMT

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:

Re: Challenge #52: Solving the Knapsack Problem

alex — Tue, 28 Feb 2017 14:56:54 GMT

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.

Re: Challenge #52: Solving the Knapsack Problem

SeanAdams — Wed, 05 Apr 2017 04:42:55 GMT

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.

- 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 :-)

Re: Challenge #52: Solving the Knapsack Problem

mceleavey — Tue, 04 Apr 2017 22:50:33 GMT

Yes, I feel I have unfinished business here too.

Re: Challenge #52: Solving the Knapsack Problem

SeanAdams — Wed, 05 Apr 2017 04:42:15 GMT

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

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

Re: Challenge #52: Solving the Knapsack Problem

estherb47 — Wed, 03 May 2017 18:52:06 GMT

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

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.

Re: Challenge #52: Solving the Knapsack Problem

mceleavey — Wed, 03 May 2017 18:55:18 GMT

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

Re: Challenge #52: Solving the Knapsack Problem

NicoleJohnson — Wed, 17 May 2017 15:29:06 GMT

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!

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

Re: Challenge #52: Solving the Knapsack Problem

LordNeilLord — Tue, 13 Jun 2017 13:32:40 GMT

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

Re: Challenge #52: Solving the Knapsack Problem

patrick_digan — Fri, 22 Sep 2017 18:17:14 GMT

I've used the combination macro to get all the combinations. From past experience, it will not scale well in terms of speed. I like my second output which shows you which boxes add up to the weight and price (1+2+3 means boxes 1, 2, and 3 were selected.)

Re: Challenge #52: Solving the Knapsack Problem

samN — Wed, 06 Dec 2017 03:45:16 GMT

I Loved this Challenge! I didn't really know what location optimization macros did or how they worked before this. I think it allows for some great use cases and hope to be able to put it to use soon! Also first time nesting macros, so thats fun

Re: Challenge #52: Solving the Knapsack Problem

ggruccio — Tue, 12 Dec 2017 04:32:10 GMT

Tried several approaches, but went the prescriptive optimization route. A bit cryptic to set up, but the tool works.

Re: Challenge #52: Solving the Knapsack Problem

LandonG — Wed, 13 Dec 2017 16:21:00 GMT

Solution attached.

Re: Challenge #52: Solving the Knapsack Problem

philipmannering — Sat, 16 Dec 2017 11:53:44 GMT

Intrigued about the combination macro someone downloaded from the gallery and used. Will have to give it a try. My solution attached

My workflow

The workflow using the macro

The macro

Re: Challenge #52: Solving the Knapsack Problem

jasperlch — Mon, 18 Dec 2017 02:05:47 GMT

Solution attached.

Re: Challenge #52: Solving the Knapsack Problem

dsmdavid — Wed, 20 Dec 2017 19:39:48 GMT

Spent most part of the morning stuck at this, trying to find a dynamic solution. Knew that an iterative was going to do the trick, but thought a batch was needed. Inspiration came after a while away from the computer....

Re: Challenge #52: Solving the Knapsack Problem

Natasha — Thu, 28 Dec 2017 01:48:56 GMT

Comparing now my solution to others I feel that I am missing something.. I did cheat a little bit for the second output and instead of doing a macro I used a sample tool, which of course won't let to produce the details for thousands of batches but does work for looking at a few options.

My solution is somewhat similar to the provided non-macro solution. I know that it doesn't consider all possible batch combinations, but I don't think we need to consider them all (Correct me if I am wrong here), as the goal is to optimise $ value, so I believe sorting desc is enough.

I've never used Optimisation tool , so looking forward to inspect it!

My all-blue-tool workflow

Re: Challenge #52: Solving the Knapsack Problem

jamielaird — Thu, 04 Jan 2018 01:15:36 GMT

Well that took a LONG time.

But I learned some new things, and that's what this is all about.

Full disclosure: after several failed attempts and many reads of the Optimizer Macro help file I reverse engineered @estherb47's solution and implemented something pretty similar. Thanks, Esther. You made it look so easy..

And a special shout out to these guys. Couldn't have done it without you.

Re: Challenge #52: Solving the Knapsack Problem

JosephSerpis — Sat, 27 Jan 2018 11:25:34 GMT

Challenge Completed