Hi,
I have following program for solving the simple solution for the knapsack 0-1 problem.
The code must contains a fault because the solutions are not good, but where is it ?
Dim capacity As Integer = 16
Dim size() As Integer = {3, 4, 7, 8, 9}
Dim values() As Integer = {4, 5, 10, 11, 13}
Dim totval(capacity) As Integer
Dim best(capacity) As Integer
Dim n As Integer = values.Length
Dim i, j As Integer
For j = 0 To n - 1
For i = 0 To capacity
If (i >= size(j)) Then
If (totval(i) < totval(i - size(j)) + values(j)) Then
totval(i) = totval(i - size(j)) + values(j)
best(i) = j
End If
End If
Next
Next
MessageBox.Show(totval(capacity).ToString) ' gives the solution value
Dim totcap As Integer = 0
i = capacity
While (totcap <= capacity)
MessageBox.Show(best(i).ToString) ' gives the choosen items
totcap += values(best(i))
i -= 1
End While
End Sub
Is there someone who can give the right code?
Thanks for any response
I have following program for solving the simple solution for the knapsack 0-1 problem.
The code must contains a fault because the solutions are not good, but where is it ?
Dim capacity As Integer = 16
Dim size() As Integer = {3, 4, 7, 8, 9}
Dim values() As Integer = {4, 5, 10, 11, 13}
Dim totval(capacity) As Integer
Dim best(capacity) As Integer
Dim n As Integer = values.Length
Dim i, j As Integer
For j = 0 To n - 1
For i = 0 To capacity
If (i >= size(j)) Then
If (totval(i) < totval(i - size(j)) + values(j)) Then
totval(i) = totval(i - size(j)) + values(j)
best(i) = j
End If
End If
Next
Next
MessageBox.Show(totval(capacity).ToString) ' gives the solution value
Dim totcap As Integer = 0
i = capacity
While (totcap <= capacity)
MessageBox.Show(best(i).ToString) ' gives the choosen items
totcap += values(best(i))
i -= 1
End While
End Sub
Is there someone who can give the right code?
Thanks for any response