Community Spring Cleaning week is here! Join your fellow Maveryx in digging through your old posts and marking comments on them as solved. Learn more here!

Weekly Challenges

Solve the challenge, share your solution and summit the ranks of our Community!

Also available in | Français | Português | Español | 日本語
IDEAS WANTED

Want to get involved? We're always looking for ideas and content for Weekly Challenges.

SUBMIT YOUR IDEA

Challenge #52: Solving the Knapsack Problem

CHarrison
8 - Asteroid

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 

justynam
8 - Asteroid

My solution, using brute force algorithm

kat
12 - Quasar
Spoiler
Probably just coincidence that the simple solution workedProbably just coincidence that the simple solution worked
OldDogNewTricks
10 - Fireball

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

 

danilang
19 - Altair
19 - Altair

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

OllieClarke
15 - Aurora
15 - Aurora

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
MarMu
8 - Asteroid

 

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
MainMainMatch MacroMatch Macro
Laurap1228
11 - Bolide

My first location optimization macro!

 

Spoiler
challenge52.jpg
cgoodman3
14 - Magnetar
14 - Magnetar

Here's my solution:

 

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

Knapsack.JPG

 

 

Chris
Check out my collaboration with fellow ACE Joshua Burkhow at AlterTricks.com
cgoodman3
14 - Magnetar
14 - Magnetar

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:
Knapsackv2.JPG
Location optimiser:
Knapsack location optimiser.JPG
Batch macro:
Knapsack batch.JPG


Chris
Check out my collaboration with fellow ACE Joshua Burkhow at AlterTricks.com