File Exchange

image thumbnail

0-1 Knapsack

version 1.4 (2.92 KB) by

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

15 Downloads

Updated

View License

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

Comments and Ratings (7)

It works perfectly, but is it possible to change the code, for the case that the values of my items are all the same and i get every combination of items who fit in the constraint?

Works perfectly.

Nithin S

I am trying to use this inside a matlab function block where weights, value and capacity of knapsack are inputs to the block. I am facing an error "Computed maximum size is not bounded.
Static memory allocation requires all sizes to be bounded."
this is happening at line A = zeros(length(weights)+1,W+1);

how do I overcome this error ?

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.

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.

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.

Updates

1.4

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

1.3

Added published demonstration file and fixed a bug

1.1

Fixed Wikipedia link

MATLAB Release
MATLAB 7.7 (R2008b)
Acknowledgements

Inspired: KP01

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video