## July 10, 2009

You can follow this conversation by subscribing to the comment feed for this post.

Brute force works for me:

```appetizer.solution <- local (
function (target) {
app <- c(2.15, 2.75, 3.35, 3.55, 4.20, 5.80)
r <- 2L
repeat {
c <- gtools::combinations(length(app), r=r, v=app, repeats.allowed=TRUE)
s <- rowSums(c)
if ( all(s > target ) ) {
print("No solution found")
break
}
x <- which( s == target )
if ( length(x) > 0L ) {
print("Solution found")
print(c[x,])
break
}
r <- r + 1L
}
})
appetizer.solution(15.05)
# [1] "No solution found"
appetizer.solution(15.15)
# [1] "Solution found"
#      [,1] [,2] [,3] [,4] [,5]
# [1,] 2.15 2.75 3.35 3.35 3.55
# [2,] 2.75 2.75 2.75 3.35 3.55
```

I canâ€™t believe I just wrote that. Must be the heat. This must be the most elementary mistake in numerical analysis. Try this version instead:

```appetizer.solution <- local (
function (target) {
app <- c(2.15, 2.75, 3.35, 3.55, 4.20, 5.80)
r <- 2L
repeat {
c <- gtools::combinations(length(app), r=r, v=app, repeats.allowed=TRUE)
s <- rowSums(c)
if ( all(s > target) ) {
print("No solution found")
break
}
x <- which( abs(s-target) < 1e-4 )
if ( length(x) > 0L ) {
print("Solution found")
print(c[x,])
break
}
r <- r + 1L
}
})
appetizer.solution(15.05)
# [1] "Solution found"
# [1] 3.55 5.80 5.80
```

I'll go and kill myself now....

Wait a minute, if repeats are allowed, then you have to have different utilities for second replicate. Decreasing marginal returns. Where are you getting your item utilities from?

A marginally better solution exists by reducing the problem 'dynamically.' I have implemented this as a program for the subset sum problem but this versio n assumed repetitions are not allowed. An adaptation to allow repeats should still work.

The program and a pdf version of a flowchart for it are available at;
www.cybase.co.uk/wlcs/Software.html

Looking at the answer given by Allan the solution is incorrect!

3.55 + 5.80 + 5.80 = 15.15

Also the answer above totals 15.15, but the original problem found no solution only as 15.15, he apparently tried again with the second target sum.

My program does not search for solutions with duplicates, but allows duplicate alues to be entered. Doubling up eaxh entry finds the solution

2.15 + 3.55 + 3.55 + 5.80 = 15.05

but the values are entered as whole numbers.

Steve

This is only a preview. Your comment has not yet been posted.

Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

## Information

R for the Enterprise

Got comments or suggestions for the blog editor?
Email David Smith.