Code covered by the BSD License

Highlights from 0-1 Knapsack

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

0-1 Knapsack

by

Petter (view profile)

26 Jan 2009 (Updated )

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

File Information
Description

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

Acknowledgements

This file inspired Kp01.

MATLAB release MATLAB 7.7 (R2008b)
27 Mar 2009 Chetan Viraktamath

Chetan Viraktamath (view profile)

12 Feb 2009 John D'Errico

John D'Errico (view profile)

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

12 Feb 2009 Petter

Petter (view profile)

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.

Comment only
10 Feb 2009 John D'Errico

John D'Errico (view profile)

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.

09 Feb 2009