# [R] ?currency challenge ?knapsack challenge ?probabilities

Polwart Calum (COUNTY DURHAM AND DARLINGTON NHS FOUNDATION TRUST) calum.polwart at nhs.net
Mon Dec 28 11:19:33 CET 2015

```Hi Jim

Working on basis of exact match.  but the 25% inncrements are rounded to imtegers, so like buying from a shop priced in whole numbers but changeis what you expect not 'roughly right'

Thanks

Calum

On 27 Dec 2015, at 22:04, Jim Lemon <drjimlemon at gmail.com<mailto:drjimlemon at gmail.com>> wrote:
Hi Calum,
Does this include an error tolerance for the match between the ordered and delivered quantities? That is, is it okay to have a maximum of one unit difference or do deliveries have to exactly match orders?

Jim

On Sun, Dec 27, 2015 at 10:08 PM, Polwart Calum (COUNTY DURHAM AND DARLINGTON NHS FOUNDATION TRUST) <calum.polwart at nhs.net<mailto:calum.polwart at nhs.net>> wrote:
I am currently working on a project that is producing Gigabyte sized vectors that kill R.  It can take 24 hours to run. So frustrating to get that far and have to scale back my inputs and rerun...

The problem i'm trying to solve as i see it is very similar to optimal currency denominations problems combined with a knapsack problem. Let me TRY to explain.

We have a product that we want to manufacture in as few sizes as possible.  like currency if you want 30cents but a 30cent coin doesnt exist you can join multiple products together. (3x10 cent, 25cent +5 cent, etc)

Unlike currency we dont need every value to be possible, we have a list of known values which are effectively related to each other by the next size up being 25% bigger. So for instance 64, 80 100.

We have some rules that say you can't use more than X products combined to make the final size.  A bit like saying never give more than 10 coins as change, so you cant issue 20x5cents for a dollar of change.

All of that fits a standard currency denomination challenge.

We dont need the combinations to be calculated using greedy method. [We will calculate and store as a table]

BUT - we do have a manufacturing limitation that means can manufacture to any whole number size, we cant do smaller than size5. (We dont go as low as that anyway... size 11 is as low as needed).  So different from any currency problem I've seen where the lowest coin size is always a 1 allowing any size to be produced.

So i have three questions I'm trying to answer:

- what is the smallest product range we can make that achieves our rules for max combinations of sizes?

- Is there a more optimal range. Say the smallest range was 4 sizes, for example 5,6,23,40.  Its possible adding a 22 and a 46 to that may actually be cheaper than supplying 2x5 and 2x6 or 2x23...

Currently I'm identifying every possible combination into a matrix.  We have a manufacturing constraint of max size 49 as well.  So i take every end user size possible (from 11 thru to 125).  For each size i then take every combination of possible sizes from 5 to 49 (45 sizes) that we COULD make and work out how i can achieve all the possible end user sizes, discarding any combinations that break our rules for max combinations.

Thats a giant set of for loops.  Once i establish the options we  can apply the manufacturing costs and usage data to find the answer.

For now 45 sizes,combined in any of up to 5 different combinations to do 10 end user sizes is creating vectors too big for R to handle...

Long explanation of the problem, to basically say... has anyone come across a function in R that might simplify this?

Sent from TypeMail<http://www.typeapp.com/r>

On 27 Dec 2015, at 08:00, "Polwart Calum (COUNTY DURHAM AND DARLINGTON NHS FOUNDATION TRUST)" <calum.polwart at nhs.net<mailto:calum.polwart at nhs.net><mailto:calum.polwart at nhs.net<mailto:calum.polwart at nhs.net>>> wrote:

********************************************************************************************************************

This message may contain confidential information. If you are not the intended recipient please inform the
sender that you have received the message in error before deleting it.
Please do not disclose, copy or distribute information in this e-mail or take any action in reliance on its contents:
to do so is strictly prohibited and may be unlawful.

NHSmail is the secure email and directory service available for all NHS staff in England and Scotland
NHSmail is approved for exchanging patient data and other sensitive information with NHSmail and GSi recipients
NHSmail provides an email address for your career in the NHS and can be accessed anywhere

********************************************************************************************************************

[[alternative HTML version deleted]]

______________________________________________
R-help at r-project.org<mailto:R-help at r-project.org> mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
and provide commented, minimal, self-contained, reproducible code.

********************************************************************************************************************

This message may contain confidential information. If you are not the intended recipient please inform the
sender that you have received the message in error before deleting it.
Please do not disclose, copy or distribute information in this e-mail or take any action in reliance on its contents:
to do so is strictly prohibited and may be unlawful.