Challenge #52: Solving the Knapsack Problem

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.

challenge_52_start_file.yxmd

challenge_52_solution.yxzp

Macros

Join

Preparation

Advanced

Data Analysis

Transform

Interface

Difficult

Accepted answers

All comments

mceleavey

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

Create all combinations.PNG

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.

Filter Cmbinations of the same box.PNG

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:

Unique combi.PNG

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:

Filter top picks.PNG

53 Solution Output.yxdb

Challenge 53 Solution.yxmd

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.

Challenge_53_AC.yxmd

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

Knapsack.yxmc

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.

challenge_52_EHB_solution.yxmd

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!

challenge_52_NicoleJohnson.yxwz

LordNeilLord

Finally got there this one...messy workflow

Spoiler

challenge_52_LNL.yxmd

patrick_digan

Spoiler

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

challenge_52_start_file.yxzp

samN

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

challenge_52.yxzp

ggruccio

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

challenge_52_gg_finish.yxmd

LandonG

Solution attached.

challenge_52_start_file.yxzp

philipmannering

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

My workflow

Spoiler

The workflow using the macro

The macro

challenge_52 - Solving the Knapsack Problem.yxzp

jasperlch

Solution attached.

challenge_52_JL.yxzp

dsmdavid

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....

solved#52.yxzp

Natasha

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!

Spoiler

My all-blue-tool workflow
Screen Shot 2017-12-28 at 01.29.30.png

challenge_52_Natasha.yxmd

jamielaird

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..

Spoiler

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

Spoiler

challenge_52_solution_JL.yxmd

JosephSerpis

Challenge Completed

Challenge_52_Joe_Serpis.yxzp

CHarrison

Absolutely killed my brain coming up with this solution, but it works!

I went one step further, and made an app out of it so the user can choose the number of items

challenge_52_start_file (1).yxmd

justynam

My solution, using brute force algorithm

challenge_52_solution_JM.yxmd

kat

Spoiler

Probably just coincidence that the simple solution worked

Challenge #52.yxmd

OldDogNewTricks

I took this as a personal challenge (excuse) to use the Optimizer tool. I see so many implications for this in the 'real world' so I wanted to get a better grasp on it and this challenge helped me with this objective.

Without these two links I would not have been able to figure it out: Optimizer tool help and Optimizer tool example (Thank you @KuoL)

I did experience some strange behavior with this tool, in that it threw an error when my variable column was not an integer; which caused me to use 2 additional tools downstream.

Spoiler

I handled this with a Macro (Input > Macro > Output). I made the max weight and number of items adjustable. Then I just modified the constraints in the constraint table accordingly based on these.

The macro outputs the individual items and their details (value and weight) as well as the summarized (number of items and total value).

challenge_52_completed.yxzp

danilang

Big, messy, brute force solution. Challenging though!

Spoiler

I generated all possible combinations of rows
Generate 52.png

then generated running totals for the weight and selected all < 15Kg and used summaries to pull out 1, 2, 3 and 4 box solutions

Analyze 52.png

Dan

challenge_52_solution_DL.yxmd

OllieClarke

I'm sure there are solutions with fewer tools, but this one is fully dynamic, which is nice.

Spoiler

Thanks to a first year lecture in set theory, I knew if I could use 2^n and convert to binary to give me every possible combination of boxes. I then feed this into a batch macro to update a filter.

I'm sure this could be done with an iterative macro, but this is the way my brain took me
Challenge 52.PNG

Challenge_52_OC_solution.yxzp

MarMu

Pretty fun exercise. Used the Optimization tool to solve the classical IP Knapsack problem. I wanted to solve the challenge in one go. To achieve this, I made a batch marco to initiate 4 executions of the same optimization leveraging the Control Parameter to dynamically change the # allowed boxes.

Spoiler

Main

Match Macro

challenge_52_start_file_MarMu.yxmd

challenge_52_start_file_MarMu_Macro.yxmc

Laurap1228

My first location optimization macro!

Spoiler

challenge_52_LP.yxzp

cgoodman

Here's my solution:

Spoiler

Using the optimisation tool now I know how to set one up with thanks to @nikolaskardasis

challenge_52_start_file_solution.yxmd

cgoodman

An improvement on the first version as it now only takes 0.5 seconds to solve.

Spoiler

I used the location optimisation macro, and then stuck this inside a batch macro to cycle through the combinations of 1,2,3,4 items (for some reason going to 5 takes ages to solve and from my previous solution I know 4 items is the max).

Workflow:

Location optimiser:
Knapsack location optimiser.JPG

Batch macro:
Knapsack batch.JPG

Wouter

For my solution I've used the Optimization Tool:

Spoiler

challenge_52_solution_WK.yxmd

danrh

Will only work to 9 boxes ... hmm ....

solution.yxmd

JoBen

Cheers!

challenge_52_Joben_Solution.yxzp

kelly_gilbert

This was a good opportunity to learn how to configure inputs for the Optimization tool. It was tricky to get the inputs set up just right!

Spoiler

Main workflow:

Batch macro:

challenge_52_solution_klg.yxzp

yajing_wang

feel the solution is not accurate as it only works for the data set provided. It does not consider the dollar/kg. In some situation, it is better to pick up the one with less dollar but much less kg box.

yajing_wang

This one take me really long time, but find out the my best and easiest way to solve this issue, I am happy! Did not consider the situation that it may better to take 2 smaller kg box than 1 heavy box....

Workflow:

Spoiler

Spoiler:
Use the idea of batch macro and process by group which make it is easier for Iteration macro and suitable for more than one case.
52 workflow.PNG