Challenge #52: Solving the Knapsack Problem

[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 

[justynam]

My solution, using brute force algorithm

[kat]

Spoiler

Probably just coincidence that the simple solution worked

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

[danilang]

Big, messy, brute force solution.  Challenging though!

Spoiler

I generated all possible combinations of rows 


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

Dan

[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

[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

MainMatch Macro

[Laurap1228]

My first location optimization macro!

Spoiler

[cgoodman3]

Here's my solution:

Spoiler

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

[cgoodman3]

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:

Batch macro: