Hi I have a question about knapsack problem and it's algorithms. I have built some code to solve 0/1 knapsack problem with Dynamic Programming and Branch and Bound. The value and weight are randomly generated. I ran the program and obtain the result showing.
Number of Items | Processing Time in milliseconds / Maximun Beneift Val
Number of Items | Greedy | D.P. | B. & B.
10 | 0/2502 | 0/2469 | 0/2469
100 | 0/22629 | 8/22621 | 0/19382
1000 | 0/202083 | 651/202081 | 30/173603
10000 | 4/2025662 |66624/2025662 |2709/1637172
So I was wondering if the result of these two algorithms can be different
I am expecting if they are different or just my code is bad
Branch and Bound is just a additional to DP, which mean you can do 0-1 knapsack without Branch and Bound. But, you can apply Branch and Bound when the weight of bag is less that 0. So it's the same algorithm.