i am researcher student. I am searching large data for knapsack problem. I wanted test my algorithm for knapsack problem. But i couldn't find large data. I need data has 1000 item and capacity is no matter. The point is item as much as huge it's good for my algorithm. Is there any huge data available in internet. Does anybody know please guys i need urgent.
+1
A:
You can quite easily generate your own data. Just use a random number generator and generate lots and lots of values. To test that your algorithm gives the correct results, compare it to the results from another known working algorithm.
Mark Byers
2010-05-22 18:15:45
you're right but thing is i have to know best solution. coz i wanted to know my algorithm can find best solution or not!
2010-05-22 18:19:36
@user347918: You can find an existing working algorithm to tell you what the best solution is, and check you get the same. Perhaps try 3 or 4 different algorithms and make sure they all agree, just in case one of them has a bug. You can for example try some of the solutions here: http://rosettacode.org/wiki/Knapsack_problem/Bounded
Mark Byers
2010-05-22 18:21:17
Thank you for your advisory. Sorry one more question. If i will test my algorithm multiknapsack problem. Is it not different than singleknapsack right ? I mean i assumed that problem has 100 itmes and 5 knapsacks . It mean can i think problem has 500 item ? Sorry don't blame i don't have experience. I am really bad researcher student :(. I am just starting now.
2010-05-24 10:03:46
@user347918: The knapsack problem generalised to more than one knapsack is called the "bin packing problem". See http://en.wikipedia.org/wiki/Bin_packing_problem
Mark Byers
2010-05-24 11:57:49
thank you for your replay
2010-05-24 19:31:17
A:
Hi,
I have the same requirement. Obviously only Brute force will give the optimal answer and that won't work for large problems. However we could pitch our algorithms against each other...
To be clear, my algorithm works for 0-1 problems (i.e. 0 or 1 of each item), Integer or decimal data. I also have a version that works for 2 dimensions (e.g. Volume and Weight vs. Value).
My file reader uses a simple CSV format (Item-name, weight, value):
X229257,9,286 X509192,11,272 X847469,5,184 X457095,4,88 etc ....
If I recall correctly, I've tested mine on 1000 items too.
Regards
Walt
PS I ran my algorithm again the problem on Rosette Code that Mark highlighted (thank you). I got the same result but my solution is much more scaleable than the dynamic programming / LP solutions and will work on much bigger problems
Walt Barker
2010-06-30 14:34:25
The editor has displayed my file format wrongly. My filereader expects one item per line. I've currently go the target weight hard-coded and will change it to whatever you are using.
Walt Barker
2010-06-30 14:38:50
Hey man, It sound very nice . Can you send to me your data ? I will run my algorithm on your data. So i will confirm results. It would be very nice work. Thank you
2010-07-01 14:52:43
also one thing actually i used LP solutions. But not much same , different from others what they did. I tested several problems everytime my method was finding best solution.
2010-07-01 14:56:17
If you drop me an email I'll send you some data. walter.barker2 at ntlworld.com
Walt Barker
2010-07-01 15:46:29
Your data is ready :-) I've generated a file with 998 items each weight 1-50kg, value $100-400. The target is 200kg.My program took 25 seconds (it varies hugely depending on the data) and produced a total value of $20430.
Walt Barker
2010-07-01 16:18:43
I've also created a file with 10,931 items... my program ran in 19 seconds :-)
Walt Barker
2010-07-01 16:31:43
Did you get my data Oyuka? I replied to your email on Friday but have not heard anything.
Walt Barker
2010-07-05 13:28:03
A:
In case anyone else wants a Large data set to test their Knapsack algorithm, I've published some data files and my results, here:
http://homepage.ntlworld.com/walter.barker2/Knapsack%20Problem.htm
I'd love to hear from anyone working on this problem, My email address is on the page.
Walt
Walt Barker
2010-07-10 18:47:02