Excel's solver would give you only one solution, I think.
In Don Knuth's Pre-Fascicle 3A you will find a solution
(exhaustive but not ideal, as he mentions) which I put
into VBA (see below).
Copy the code into the VBA editor, run it and press CTRL G
to see the results.
HTH,
Bernd
--------- Snipp here for code -------------
Option Explicit
'Knuth fasc3a.pdf, page 11 of 65, Filling a rucksack
Sub Fill_Rucksack()
Const n As Long = 7
Dim w(0 To n) As Long
Dim delta(1 To n) As Long 'delta(j) = w(j) - w(j-1) for 1
<= j < n
Dim t As Long
Const NCap As Long = 40
Dim c(0 To n) As Long
Dim r As Long
Dim i As Long
Dim length As Long
w(0) = 0
w(1) = 3
w(2) = 3
w(3) = 4
w(4) = 7
w(5) = 10
w(6) = 20
w(7) = 26
F1: 'Initialize
t = 0
c(0) = n
r = NCap
F2: 'Visit
'Visit the combination c(0)...c(t), which uses NCap -
r units of capacity
length = 0
For i = 0 To t
length = length + w(c(i))
Next i
If length <= NCap And w(c(t)) < 0 Then
Debug.Print "Solution: ";
For i = 0 To t: Debug.Print "["; c(i); "]"; w(c
(i));: Next i
Debug.Print
End If
F3: 'Try to add w(0)
If c(t) 0 And r = w(0) Then
t = t + 1
c(t) = 0
r = r - w(0)
GoTo F2
End If
F4: 'Try to increase c(t)
If t = 0 Then
GoTo Terminate
End If
If c(t - 1) c(t) + 1 And r = delta(c(t) + 1) Then
c(t) = c(t) + 1
r = r - delta(c(t))
GoTo F2
End If
F5: 'Remove c(t)
r = r + w(c(t))
t = t - 1
GoTo F4
Terminate:
End Sub
---------- Snipp here for solutions ----------
Solution: [ 7 ] 26
Solution: [ 7 ] 26 [ 1 ] 3
Solution: [ 7 ] 26 [ 2 ] 3
Solution: [ 7 ] 26 [ 2 ] 3 [ 1 ] 3
Solution: [ 7 ] 26 [ 3 ] 4
Solution: [ 7 ] 26 [ 3 ] 4 [ 1 ] 3
Solution: [ 7 ] 26 [ 3 ] 4 [ 2 ] 3
Solution: [ 7 ] 26 [ 3 ] 4 [ 2 ] 3 [ 1 ] 3
Solution: [ 7 ] 26 [ 4 ] 7
Solution: [ 7 ] 26 [ 4 ] 7 [ 1 ] 3
Solution: [ 7 ] 26 [ 4 ] 7 [ 2 ] 3
Solution: [ 7 ] 26 [ 4 ] 7 [ 2 ] 3 [ 1 ] 3
Solution: [ 7 ] 26 [ 4 ] 7 [ 3 ] 4
Solution: [ 7 ] 26 [ 4 ] 7 [ 3 ] 4 [ 1 ] 3
Solution: [ 7 ] 26 [ 4 ] 7 [ 3 ] 4 [ 2 ] 3
Solution: [ 7 ] 26 [ 5 ] 10
Solution: [ 7 ] 26 [ 5 ] 10 [ 1 ] 3
Solution: [ 7 ] 26 [ 5 ] 10 [ 2 ] 3
Solution: [ 7 ] 26 [ 5 ] 10 [ 3 ] 4
|