Code covered by the BSD License  

Highlights from
0-1 Knapsack

5.0

5.0 | 3 ratings Rate this file 26 Downloads (last 30 days) File Size: 3.94 KB File ID: #22783

0-1 Knapsack

by Petter

 

26 Jan 2009 (Updated 12 Feb 2009)

Solves the 0-1 knapsack problem with positive integer weights.

| Watch this File

File Information
Description

Uses dynamic programming to solve the problem, see for example http://en.wikipedia.org/wiki/Knapsack_problem .

Acknowledgements
This submission has inspired the following:
KP01
MATLAB release MATLAB 7.7 (R2008b)
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (4)
10 Feb 2009 John D'Errico

Please let others rate your work. Rating your own stuff highly says nothing about the code, but perhaps drops you closer to the level of a spammer on the FEX like Marco. So let the rating system do its job. I know that you think your stuff is good. So does every eager high school student who posts their last homework assignment.

In the particular case of this utility. I'll first suggest that there is no reason to publish the code for knapsack itself. See there was an error generated when you tried it.

How about the help? It too is lacking. It is not terrible, but still lacking. Here is the relevant part of the help block.

% [AMOUNT] = KNAPSACK(WEIGHTS, VALUES, CONSTRAINT)
%
% WEIGHTS : The weight of every item
% VALUES : The value of every item
% CONSTRAINT : The weight constraint of the knapsack
%
% BEST : Value of best possible knapsack
% AMOUNT : The amount to use of each item (0 or 1)

See that there appear to be two return arguments, but your help does not tell us what order they are in. In fact, when only one output argument is returned, it looks to be the second of the two outputs. I won't suggest what your code actually does. That is your job.

There was a nicely written H1 line in the help. Well done in that respect. I also found error checks in the code.

Finally, the best code would include a simple example in the help itself. I know, you will claim there is one in the demo file. But when people actually download this, they will often look to the help rather than search for some other file.

12 Feb 2009 Petter

Thanks for the suggestions. A new version has been uploaded.

I am sometimes annoyed by the fact that I have to download and unpacka .zip file before looking at code for an algorithm. Publishing knapsack.m itself provided a way for the user to view the code without downloading anything. But the error looke unprofessional and it has been removed.

12 Feb 2009 John D'Errico

Fast, it seems to work. Help is good. Problems are repaired. I can't ask for more.

27 Mar 2009 Chetan Viraktamath  
Please login to add a comment or rating.
Updates
09 Feb 2009

Fixed Wikipedia link

09 Feb 2009

Added published demonstration file and fixed a bug

12 Feb 2009

Updated the help description. Decreased the number of published files.

Tag Activity for this File
Tag Applied By Date/Time
knapsack Petter 26 Jan 2009 15:48:16
dynamic programming Petter 26 Jan 2009 15:48:16
01 knapsack Petter 12 Feb 2009 16:48:42

Contact us at files@mathworks.com