Question knapsack program

andrews

Well-known member
Joined
Nov 22, 2011
Messages
132
Programming Experience
5-10
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
 
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 ?

I would love to try and help here but my own Knapsack program only adds Beef Sandwiches, a bit of Fruit, a few Biscuits and a Bottle of Pop whenever I run it which I do not think will help since your Knapsack program seems to be using numbers?

If you would like to add an explanation of what your "Knapsack 0-1" program is supposed to be doing, along with what it's currently doing and what's going wrong then I am sure that someone here may be able to give you some valuable advice.

Cheers,

Ian

BTW, I am sure you have made enough posts by now to know that when posting code you should be using Code tags for readability?
 
Ian,
The Beef Sandwiches, a bit of Fruit, a few Biscuits and a Bottle of Pop are in my program the indexes of the arrays size and values.
If somebody could help, knowing well the knapsack problem, I suppose that there must no explanation what I am expecting from this program.
But what is going wrong in the code I do not know , but I know that the results are not good.
I am looking now to another program who seems to be better but the data structures are different but I am not still ready.
Ian, thanks for your response
 
Back
Top